
//顺时针打印矩阵
//public class Printer {
//    public int[] clockwisePrint(int[][] mat,int n,int m) {
//        int[] a =new int[m*n];
//        if( mat ==null) return a;
//        int i =0;
//        int j =0;
//        int k =0;
//        int startX =0;
//        int startY =0;
//        int endX = n -1;
//        int endY = m -1;
//        while( startX <= endX && startY <= endY ){
//            //如果只剩下一行
//            if( startX == endX ){
//                for( ;j <= endY;j++,k++){
//                    a[k] = mat[startX][j];
//                }
//                return a;
//            }
//            //如果只剩下一列
//            if( startY == endY ){
//                for( ; i    <= endX ; i++,k++){
//                    a[k] =    mat[i][startY];
//                }
//                return a;
//            }
//            //将矩阵上边除右顶点添加到返回的数组中
//            for( ; j < endY ; j++,k++){
//                 a[k] = mat[i][j];
//            }
//               //将矩阵右边除边下顶点添加到返回的数组中
//            for( ; i < endX ; i++,k++){
//                 a[k] = mat[i][j];
//            }
//              //将矩阵下边除边左顶点添加到返回的数组中
//            for( ; j > startX ; j--,k++){
//                 a[k] =    mat[i][j];
//            }
//                 //将矩阵左边除边上顶点添加到返回的数组中
//            for( ; i > startY ; i--,k++){
//                 a[k] = mat[i][j];
//            }
//            i++;
//            j++;
//            startX++;
//            startY++;
//            endX--;
//            endY--;
//       }
//       return a;
//    }
//}

//左右最值最大差
//public class MaxGap {
//    public int findMaxGap(int[] A, int n) {
//        int leftmax = 0,rightmax = 0,value = 0,temp = 0;
//        for(int k = 0;k < n-1;k++){
//            if(value != 0 && A[k] > leftmax){
//                leftmax = A[k];
//            }else{
//                leftmax = A[0];
//                for(int i = 0;i <= k;i++){
//                    leftmax = A[i] > leftmax ? A[i] : leftmax;
//                }
//            }
//            rightmax = A[k + 1];
//            for(int j = k+1;j < n;j++){
//                rightmax = A[j] > rightmax ? A[j] : rightmax;
//            }
//            value = leftmax - rightmax;
//            value =value < 0 ? -value : value;
//            temp = value > temp ? value : temp;
//        }
//        return temp;
//    }
//}

// 马戏团
//public class Main {
//
//    static class People {
//        int height;
//        int weight;
//
//        public People(int weight, int height) {
//            this.height = height;
//            this.weight = weight;
//        }
//    }
//
//    public static void main(String[] args) {
//
//        Scanner scan = new Scanner(System.in);
//        while (scan.hasNext()) {
//            int n = scan.nextInt();
//            People[] array = new People[n];
//            for (int i = 0; i < n; ++i) {
//                int index = scan.nextInt();
//                array[index - 1] = new People(scan.nextInt(), scan.nextInt());
//            }
//
//            Arrays.sort(array, new Comparator<People>() {
//                public int compare(People p1, People p2) {
//                    int result = Integer.compare(p1.height, p2.height);
//                    if (result != 0)
//                        return result;
//                    else
//                        return Integer.compare(p1.weight, p2.weight);
//                }
//            });
//
//            int[] dp = new int[n];
//            int max = Integer.MIN_VALUE;
//            for (int i = 0; i < dp.length; ++i) {
//                dp[i] = 1;
//                for (int j = i - 1; j >= 0; --j) {
//                    if (array[i].weight > array[j].weight
//                        || (array[i].weight == array[j].weight && array[i].height == array[j].height)) {
//                        dp[i] = Math.max(dp[i], dp[j] + 1);
//                    }
//                }
//                max = Math.max(dp[i], max);
//            }
//            System.out.println(max);
//        }
//    }
//}


// 合唱团
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int[] arr = new int[n+1];
//            for(int i = 1;i <= n;i++){
//                arr[i] = sc.nextInt();
//            }
//            int k = sc.nextInt();
//            int d = sc.nextInt();
//            long[][] fmax = new long[k+1][n+1];
//            long[][] fmin = new long[k+1][n+1];
//            long res = Integer.MIN_VALUE;
//            for(int i = 1;i <= n;i++){
//                fmax[1][i] = arr[i];
//                fmin[1][i] = arr[i];
//                for(int m = 2;m <= k;m++){
//                    for(int j = i - 1;j > 0 && i - j <= d;j--){
//                        fmax[m][i] = Math.max(fmax[m][i],Math.max(fmax[m-1][j] * arr[i],fmin[m-1][j] * arr[i]));
//                        fmin[m][i] = Math.min(fmin[m][i],Math.min(fmax[m-1][j] * arr[i],fmin[m-1][j] * arr[i]));
//                    }
//                }
//                res = Math.max(res,fmax[k][i]);
//            }
//            System.out.println(res);
//        }
//    }
//}


//简单错误记录
//public class Main{
//	public static void main(String[] args) {
//		Scanner sc=new Scanner(System.in);
//		Map<String, Integer> map=new LinkedHashMap<String, Integer>();
//		while(sc.hasNext()){
//			String str=sc.next();
//			int linenum=sc.nextInt();
//			String[] arr=str.split("\\\\");  //根据\切割
//			String s=arr[arr.length-1];
//			if(s.length()>16)  //截取
//				s=s.substring(s.length()-16);
//			String key=s+" "+linenum;
//			int value=1;
//			if(map.containsKey(key))
//				map.put(key, map.get(key)+1);
//			else {
//				map.put(key, value);
//			}
//		}
//		int count=0;
//		for(String string:map.keySet()){
//			count++;
//			if(count>(map.keySet().size()-8)) //输出最后八个记录
//			    System.out.println(string+" "+map.get(string));
//		}
//	}
//}

//数组中出现次数超过一半的数字
//public class Solution {
//    public int MoreThanHalfNum_Solution(int [] array) {
//        Map<Integer,Integer> map = new HashMap<>();
//        for(int i = 0;i < array.length;i++){
//            if(!map.containsKey(array[i])){
//                map.put(array[i],1);
//            }else{
//                map.put(array[i],map.get(array[i])+1);
//            }
//        }
//        int res = -1;
//        for(int i = 0;i < array.length;i++){
//            if(map.get(array[i]) > array.length/2){
//                res = array[i];
//                break;
//            }
//        }
//        return res;
//    }
//}


//查找兄弟单词
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String[] words = new String[n];
//            for(int i = 0;i < n;i++){
//                words[i] = sc.next();
//            }
//            Arrays.sort(words);
//            String x = sc.next();
//            char[] charX = x.toCharArray();
//            Arrays.sort(charX);
//            int k = sc.nextInt();
//            int count = 0;
//            String res = "";
//            for(String s : words){
//                if(x.equals(s)){
//                    continue;
//                }
//                if(x.length() == s.length()){
//                    boolean flag = true;
//                    char[] charS = s.toCharArray();
//                    Arrays.sort(charS);
//                    for(int i = 0;i < charS.length;i++){
//                        if(charS[i] != charX[i]){
//                            flag = false;
//                            break;
//                        }
//                    }
//                    if(flag){
//                        count++;
//                        if(count == k){
//                            res = s;
//                        }
//                    }
//                }
//            }
//            if(count == 0){
//                System.out.println("0");
//            }else{
//                System.out.println(count);
//                if(k <= count){
//                    System.out.println(res);
//                }
//            }
//        }
//    }
//}

//乒乓球筐
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            boolean flag = true;
//            StringBuilder a = new StringBuilder(sc.next());
//            char[] b = sc.next().toCharArray();
//            for(char c : b){
//                int index = a.indexOf(String.valueOf(c));
//                if(index != -1){
//                    a.deleteCharAt(index);
//                }else{
//                    System.out.println("No");
//                    flag = false;
//                    break;
//                }
//            }
//            if(flag == true){
//                System.out.println("Yes");
//            }
//        }
//        sc.close();
//    }
//}


//单词倒排
//public class Main{
//    public static void  main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String[] arr = sc.nextLine().split("[^a-zA-Z]+");
//            StringBuilder sb = new StringBuilder();
//            for(int i = arr.length-1;i>=0;i--){
//                sb.append(arr[i] +" ");
//            }
//            System.out.println(sb.toString().trim());
//        }
//        sc.close();
//    }
//}

// 骆驼命名法
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String s = sc.nextLine();
//            StringBuilder sb = new StringBuilder();
//            for(int i = 0;i < s.length();i++){
//                char ch = s.charAt(i);
//                if(ch == '_'){
//                    i++;
//                    ch = Character.toUpperCase(s.charAt(i));
//                }
//                sb.append(ch + "");
//            }
//            System.out.println(sb.toString());
//        }
//        sc.close();
//    }
//}

//求和
//public class Main{
//	static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
//	static ArrayList<Integer> list = new ArrayList<>();
//	public static void main(String[] args){
//		Scanner sc = new Scanner(System.in);
//		int n, m;
//
//		while(sc.hasNext()) {
//			n = sc.nextInt();
//			m = sc.nextInt();
//			dfs(1, m, n);
//			for(ArrayList<Integer> l : res) {
//				int i = 0;
//				for(; i < l.size() - 1; i++) {
//					System.out.print(l.get(i) + " ");
//				}
//				System.out.println(l.get(i));
//			}
//		}
//	}
//
//	public static void dfs(int index, int count, int n) {
//		if(count == 0) {
//			res.add(new ArrayList<>(list));
//		}
//		else {
//			for(int i = index; i <= count && i <= n; i++) {
//				list.add(i);
//				dfs(i + 1, count - i, n);
//				list.remove(list.size() - 1);
//			}
//		}
//	}
//}

//电话号码
//public class Main{
//    public static void main(String[] args){
//        String symbol = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
//        String number = "222333444555666777788899991234567890";
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n =  Integer.parseInt(sc.nextLine());
//            ArrayList<String> list = new ArrayList<>();
//            for(int i = 0;i < n;i++){
//                String str = sc.nextLine();
//                str = str.replace("-","");
//                String ret = "";
//                for(int j = 0;j < str.length();j++){
//                    ret += number.charAt(symbol.indexOf(str.charAt(j)+""));
//                }
//                ret = ret.substring(0,3) + "-" + ret.substring(3,7);
//                if(!list.contains(ret)){
//                    list.add(ret);
//                }
//            }
//            Collections.sort(list);
//            for(int j = 0;j < list.size();j++){
//                System.out.println(list.get(j));
//            }
//            System.out.println();
//        }
//        sc.close();
//    }
//}

//走迷宫
//public class Main{
//    static int[][] direction = {{0,-1},{-1,0},{0,1},{1,0}};
//    private static void dfs(int x,int y,char[][] maze,int[][] map){
//        for(int i = 0;i < 4;i++){
//            int xx = x + direction[i][0];
//            int yy = y + direction[i][1];
//            if(xx >= 0 && xx < 10 && yy >= 0
//               && yy < 10 && maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
//                map[xx][yy] = map[x][y]+1;
//                dfs(xx,yy,maze,map);
//            }
//        }
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            char[][] maze = new char[10][10];
//            int[][] map = new int[10][10];
//            for(int i = 0;i < 10;i++){
//                String s = sc.nextLine();
//                for(int j = 0;j < 10;j++){
//                    maze[i][j] = s.charAt(j);
//                    map[i][j] = Integer.MAX_VALUE;
//                }
//            }
//            map[0][1] = 0;
//            dfs(0,1,maze,map);
//            System.out.println(map[9][8]);
//        }
//        sc.close();
//    }
//}


//解读密码
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            StringBuilder sb = new StringBuilder();
//            for(int i = 0;i < str.length();i++){
//                char ch = str.charAt(i);
//                if(Character.isDigit(ch)){
//                    sb.append(ch);
//                }
//            }
//            System.out.println(sb.toString());
//        }
//    }
//}

//Emacs计算器
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            String[] s = sc.nextLine().split(" ");
//            Stack<Integer> stack = new Stack<>();
//            for(int i = 0;i < s.length;i++){
//                String ch = s[i];
//                if(isOperator(ch)){
//                    int num2 = stack.pop();
//                    int num1 = stack.pop();
//                    switch(ch){
//                        case "+":
//                            stack.push(num1 + num2);
//                            break;
//                        case "-":
//                             stack.push(num1 - num2);
//                             break;
//                        case "*":
//                             stack.push(num1 * num2);
//                             break;
//                        case "/":
//                             stack.push(num1 / num2);
//                             break;
//                     }
//                }else{
//                    stack.push(Integer.parseInt(ch));
//                }
//            }
//            System.out.println(stack.pop());
//        }
//
//    }
//    public static boolean isOperator(String s){
//        if(s.equals("+") || s.equals("-")|| s.equals("*") || s.equals("/")){
//            return true;
//        }
//        return false;
//    }
//}

//五子棋
//public class Main{
//    static int[][] direction= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            Character[][] map = new Character[20][20];
//            for(int i = 0;i < 20;i++){
//                String s = sc.next();
//                for(int j = 0;j < 20;j++){
//                    map[i][j] = s.charAt(j);
//                }
//            }
//            if(check(map)) System.out.println("Yes");
//            else System.out.println("No");
//        }
//    }
//    public static boolean check(Character[][] map){
//        for(int i = 0;i < 20;i++){
//            for(int j = 0;j < 20;j++){
//                if(map[i][j] == '*' || map[i][j] == '+'){
//                    for(int k = 0;k < 8;k++){
//                        int count = 1;
//                        int x = i + direction[k][0];
//                        int y = j + direction[k][1];
//                        while(x >= 0 && x < 20 && y >= 0 && y < 20 && map[x][y] == map[i][j]){
//                            count++;
//                            x += direction[k][0];
//                            y += direction[k][1];
//                        }
//                        if(count >= 5) return true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//}

// 最长上升序列
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0;i < n;i++){
//                arr[i] = sc.nextInt();
//            }
//            System.out.println(longest(arr,n));
//        }
//    }
//    public static int longest(int[] arr,int n){
//        if(arr == null || n <= 0 || arr.length!=n){
//            return 0;
//        }
//        int[] dp = new int[n];
//        dp[0] = 1;
//        int max = 1;
//        for(int i = 1;i<n;i++){
//            dp[i] = 1;
//            for(int j = i -1;j >= 0;j--){
//                if(arr[i] > arr[j]){
//                    dp[i] = Math.max(dp[i],dp[j]+1);
//                }
//            }
//            if(max < dp[i]){
//                max = dp[i];
//            }
//        }
//        return max;
//    }
//}

// 发邮件
//public class Main{
//    public static void main(String[] args){
//        long[] c = new long[22];
//        c[2] = 1;
//        c[3] = 2;
//        for(int i = 4;i < 22;i++){
//            c[i] = (i-1)*(c[i-1] + c[i-2]);
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            System.out.println(c[n]);
//        }
//    }
//}

//最长公共子序列
//public class Main{
//    public static void main(String[] args){
//        Scanner in=new Scanner(System.in);
//        while(in.hasNext()){
//            String s1=in.next();
//            String s2=in.next();
//            int[] dp=new int[s2.length()+1];
//            for(int i=0;i<s1.length();i++){
//                int pre=dp[0];
//                for(int j=1;j<=s2.length();j++){
//                    int temp=dp[j];
//                    if(s1.charAt(i)==s2.charAt(j-1))
//                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre+1));
//                    else
//                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre));
//                    pre=temp;
//                }
//            }
//            System.out.println(dp[s2.length()]);
//        }
//        in.close();
//    }
//}


//字符串计数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            long ret = 0;
//            String s1 = sc.next();
//            String s2 = sc.next();
//            int len1 = sc.nextInt();
//            int len2 = sc.nextInt();
//            int maxLen = s1.length() > s2.length() ? s1.length() : s2.length();
//            int minLen = s1.length() > s2.length() ? s2.length() : s1.length();
//            for(int i = 0;i < maxLen;i++){
//                int distance;
//                if(i < minLen){
//                    distance = s2.charAt(i) - s1.charAt(i);
//                }else{
//                    if(s1.length() > s2.length()){
//                        distance = 'a' - s1.charAt(i) - 1;
//                    }else{
//                        distance = s2.charAt(i) - 'a' + 1;
//                    }
//                }
//                long now = 0;
//                for(int j = len1;j <= len2;j++){
//                    if(j - i -1 >= 0){
//                        now = now +(long)Math.pow(26,j-i-1);
//                    }
//                }
//                now =(now * distance)%1000007;
//                ret += now;
//            }
//            System.out.println(ret - 1);
//        }
//    }
//}


//蘑菇阵
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int m = sc.nextInt();
//            int k = sc.nextInt();
//            boolean[][] map = new boolean[n][m];
//            for(int i = 0;i < k;i++){
//                int x = sc.nextInt()-1;
//                int y = sc.nextInt()-1;
//                map[x][y] = true;
//            }
//            double[][] cw = new double[n][m];
//            cw[0][0] = 1;
//            for(int i = 0;i < n;i++){
//                for(int j = 0;j < m;j++){
//                    if(map[i][j]){
//                        cw[i][j] = 0;
//                    }else if(i == 0 && j == 0){
//
//                    }else{
//                        cw[i][j] = (j-1 < 0 ? 0 : (i+1 < n ? cw[i][j-1]*0.5 : cw[i][j-1]))+(i-1 < 0 ? 0 :(j + 1 < m ? cw[i-1][j]*0.5 : cw[i-1][j]));
//                    }
//                }
//            }
//            double res = cw[n-1][m-1];
//            System.out.println(String.format("%.2f",res));
//        }
//    }
//}


//红与黑
//public class Main{
//    static class Node{
//        int x;
//        int y;
//        public Node(int x,int y){
//            this.x = x;
//            this.y = y;
//        }
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int m = sc.nextInt();
//            int n = sc.nextInt();
//            sc.nextLine();
//            Character[][] map = new Character[m][n];
//            Node start = null;
//            for(int i = 0;i < m;i++){
//                String s = sc.nextLine();
//                for(int j = 0;j < n;j++){
//                    map[i][j] = s.charAt(j);
//                    if(s.charAt(j) == '@'){
//                        start = new Node(i,j);
//                    }
//                }
//            }
//            int[][] direction = {{0,1},{0,-1},{1,0},{-1,0}};
//            bfs(map,direction,start);
//        }
//    }
//    public static void bfs(Character[][] map,int[][] direction,Node start){
//        Queue<Node> queue = new LinkedList<>();
//        boolean[][] visited = new boolean[map.length][map[0].length];
//        queue.add(start);
//        visited[start.x][start.y] = true;
//        int count = 1;
//        while(!queue.isEmpty()){
//            Node cur= queue.poll();
//            for(int i = 0;i < 4;i++){
//                Node next = new Node(cur.x + direction[i][0],cur.y + direction[i][1]);
//                if(next.x>=0 && next.x < map.length && next.y >=0 && next.y < map[0].length && map[next.x][next.y]!= '#' && !visited[next.x][next.y]){
//                    count++;
//                    queue.add(next);
//                    visited[next.x][next.y] = true;
//                }
//            }
//        }
//        System.out.println(count);
//    }
//}

// mkdir
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String[] str = new String[n];
//            for(int i = 0;i < n;i++){
//                str[i] = sc.next();
//            }
//            Arrays.sort(str);
//            List<String> res = new ArrayList<>();
//            for(int i = 1;i < n;i++){
//                if(!str[i].startsWith(str[i-1] +"/")){
//                    res.add(str[i-1]);
//                }
//            }
//            res.add(str[n-1]);
//            for(String s:res){
//                System.out.println("mkdir -p " + s);
//            }
//            System.out.println();
//        }
//        sc.close();
//    }
//}

// 数据库连接池
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            String[] str = new String[n];
//            Stack<String> stack = new Stack<>();
//            int max = 0;
//            for(int i = 0;i < n;i++){
//                str[i] = sc.nextLine();
//                if(!str[i].contains("disconnect")){
//                    stack.push(str[i]);
//                    max = Math.max(max,stack.size());
//                }else{
//                    stack.pop();
//                }
//            }
//            System.out.println(max);
//        }
//        sc.close();
//    }
//}

//Pre-Post - 牛客
//public class Main{
//    private static long num=1;
//    private static long numArr[];
//
//    private static void initArr(){
//        numArr=new long[21];
//        numArr[0]=1;
//        for(int i=1;i<21;i++){
//            numArr[i]=numArr[i-1]*i;
//        }
//    }
//
//    private static long CaculateCom(int subNum,int n){
//        return numArr[n]/(numArr[n-subNum]*numArr[subNum]);
//    }
//
//    public static void main(String[] args){
//        Scanner scanner=new Scanner(System.in);
//        initArr();
//        while(scanner.hasNext()){
//            int n=scanner.nextInt();
//            String preOrder=scanner.next();
//            String postOrder=scanner.next();
//            num=1;
//            CaculateTree(n,preOrder,postOrder);
//            System.out.println(num);
//        }
//    }
//
//    private static void CaculateTree(int n,String preOrder,String postOrder){
//        int len=preOrder.length();
//        if(len==1){
//            return;
//        }
//        int count=0;
//        preOrder=preOrder.substring(1);
//        postOrder=postOrder.substring(0,len-1);
//        while(!"".equals(preOrder)){
//            int index=postOrder.indexOf(preOrder.charAt(0))+1;
//            String newPre=preOrder.substring(0,index);
//            String newPost=postOrder.substring(0,index);
//            preOrder=preOrder.substring(index);
//            postOrder=postOrder.substring(index);
//            count++;
//            CaculateTree(n,newPre,newPost);
//        }
//        num*=CaculateCom(count,n);
//    }
//
//}

// 抄送列表
//public class Main {
//	public static void main(String[] args) {
//		Scanner in = new Scanner(System.in);
//		while(in.hasNext()){
//			String str=in.nextLine();
//			String verStr=in.nextLine();
//			char[] cA = str.toCharArray();
//			int len=str.length();
//			LinkedList<String> list=new LinkedList<String>();
//			StringBuilder sb=new StringBuilder();
//			int count=0;
//			for (int i = 0; i < len; i++) {
//				char c = cA[i];
//				if(c=='"'){
//					count++;
//				}
//				else{
//					if(count==1){
//						sb.append(c);
//					}
//					else if(count==0){
//						if(c==','){
//							list.add(sb.toString());
//							sb=new StringBuilder();
//						}
//						else{
//							sb.append(c);
//						}
//					}
//				}
//
//				if(count==2){
//					list.add(sb.toString());
//					sb=new StringBuilder();
//					count=0;
//					i++;//避免间隔符--逗号
//				}
//				else if(i==len-1){//最后一组不是引号组
//					list.add(sb.toString());
//				}
//			}
//
//			int size=list.size();
//			String sArr[]=new String[size];
//			for (int i = 0; i < size; i++) {
////				System.out.println(list.get(i));
//				sArr[i]=list.get(i);
//			}
//
//			boolean flag=false;
//			for (int i = 0; i < size; i++) {
//				if(sArr[i].equals(verStr)){
//					System.out.println("Ignore");
//					flag=true;
//					break;
//				}
//			}
//
//			if(flag){
//				continue;
//			}
//			else{
//				System.out.println("Important!");
//			}
//		}
//	}
//}


//年会抽奖
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            float ret = (count(n)/probability(n))*100;
//            System.out.println(String.format("%.2f",ret)+"%");
//        }
//        sc.close();
//    }
////     得到分子
//    public static float count(int n){
//        if(n == 1){
//            return 0;
//        }
//        if(n == 2){
//            return 1;
//        }else{
//            return (n-1) * (count(n-1) + count(n-2));
//        }
//    }
////     得到分母
//    public static float probability(int n){
//        if(n == 0){
//            return 1;
//        }else{
//            return n*probability(n-1);
//        }
//    }
//}


//养兔子
//public class Main{
//    private static Map<Integer,Long> map = new HashMap<>();
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n =  sc.nextInt();
//            long a = 1;
//            long b = 2;
//            long c = 0;
//            if(n < 3){
//                System.out.println(n);
//            }else{
//                if(map.containsKey(n)){
//                    System.out.println(map.get(n));
//                }else{
//                    for(int i =3;i <= n;i++){
//                        c = a + b;
//                        map.put(i,c);
//                        a = b;
//                        b = c;
//                    }
//                    System.out.println(c);
//                }
//            }
//        }
//        sc.close();
//    }
//}

// 收件人列表
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            String[] arr = new String[n];
//            for(int i = 0;i < n;i++){
//                String s = sc.nextLine();
//                if(s.contains(",") || s.contains(" ")){
//                    s = "\"" + s + "\"";
//                }
//                arr[i] = s;
//            }
//            for(int i = 0;i < n;i++){
//                if(i == n - 1){
//                    System.out.println(arr[i]);
//                }else{
//                    System.out.printf(arr[i]+", ");
//                }
//            }
//        }
//    }
//}

//客似云来
//public class Main{
//    private static Map<Integer,Long> map = new HashMap<>();
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int from = sc.nextInt();
//            int to = sc.nextInt();
//            long count = 0;
//            for(int i = from;i <= to;i++){
//                count = count + getPersonCount(i);
//            }
//            System.out.println(count);
//        }
//        sc.close();
//    }
//    public static long getPersonCount(int day){
//        if(day<3){
//            return 1;
//        }
//        long a = 1;
//        long b = 1;
//        long c = 0;
//        if(map.containsKey(day)){
//            return map.get(day);
//        }else{
//            for(int i = 3;i <= day;i++){
//                c = a + b;
//                map.put(i,c);
//                a = b;
//                b = c;
//            }
//            return c;
//        }
//    }
//}


// 剪花布条
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String s = sc.next();
//            String t = sc.next();
//            int count = 0;
//            while(s.contains(t)){
//                s = s.replaceFirst(t,"");
//                count++;
//            }
//            System.out.println(count);
//        }
//    }
//}

// 斐波那契凤尾
//public class Main{
//    static int[] fib = new int[100001];
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        fib[0] = 1;
//        fib[1] = 1;
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            System.out.printf((n < 25 ? "%d\n":"%06d\n"),getFibonacci(n));
//        }
//        sc.close();
//    }
//    static int getFibonacci(int n){
//        if(fib[2] == 0){
//            for(int i = 2;i < 100001;i++){
//                fib[i] = (fib[i-1] + fib[i-2])% 1000000;
//            }
//        }
//        return fib[n];
//    }
//}


// 淘宝网店
//public class Main{
////         平均一年每个月份的收入
//    static int[] moneyOfMonth = {62,28,31,60,31,60,31,62,60,62,30,62};
////         判断闰年
//    public static boolean isLeap(int year){
//        if(year % 400 == 0 || year % 4 == 0 && year % 100 != 0){
//            return true;
//        }
//        return false;
//    }
////     判断素数月
//    public static boolean isPrime(int month){
//        if(month == 2 || month == 3 || month == 5 || month == 7 || month == 11){
//            return true;
//        }
//        return false;
//    }
////     计算完整一年的收入
//    public static int moneyOfYear(int year){
//        int ret = 0;
//        for(int i = 0;i < moneyOfMonth.length;i++){
//            ret += moneyOfMonth[i];
//        }
//        if(isLeap(year)){
//            return ret + 1;
//        }
//        return ret;
//    }
////     计算同年收入
//    public static int moneyOfIncompleteYear(int[] from,int[] to){
////         同月
//        if(from[1] == to[1]){
//            if(isPrime(from[1])){
//                return to[2] - from[2]+1;
//            }else{
//                return 2 * (to[2] - from[2] + 1);
//            }
//        }
//        int ret = 0;
////         1、计算 from 月收入
//        if(isPrime(from[1])){
//            ret += moneyOfMonth[from[1]-1] - (from[2] - 1);
//        }else{
//            ret += moneyOfMonth[from[1]-1] - 2*(from[2] - 1);
//        }
//        if(from[1] == 2 && isLeap(from[0])) ret++;
////         2、计算从from当月的下一月到to的前一月这几月完整的月收入
//        for(int i = from[1];i < to[1]-1;i++){
//            ret += moneyOfMonth[i];
//            if(i == 2 && isLeap(from[0])){
//                ret++;
//            }
//        }
////         计算 to 月收入
//        if(isPrime(to[1])){
//            ret += to[2];
//        }else{
//            ret += 2 * to[2];
//        }
//        return ret;
//    }
////     计算从from 到to的收入
//    public static int money(int[] from,int[] to){
////         同年
//        if(from[0] == to[0]){
//            return moneyOfIncompleteYear(from,to);
//        }
//        int ret = 0;
////         1、计算 from 当年的输入
//        if(isPrime(from[1])){
//            ret += moneyOfMonth[from[1]-1] - from[2]-1;
//        }else{
//            ret += moneyOfMonth[from[1]-1] - 2 * (from[2]-1);
//        }
//        if(from[1] == 2 && isLeap(from[0])) ret++;
//        for(int i = from[1]; i < 12;i++){
//            ret += moneyOfMonth[i];
//            if(i == 1 && isLeap(from[0])) ret++;
//        }
////         2、计算从 from当年的下一年到to的前一年这几年完整的年收入
//        for(int i =  from[0] + 1;i < to[0];i++){
//            ret += moneyOfYear(i);
//        }
////         3、计算 to当年的收入
//        for(int i = 0;i < to[1] - 1;i++){
//            ret += moneyOfMonth[i];
//            if(i == 1 && isLeap(to[0])) ret++;
//        }
//        if(isPrime(to[1])){
//            ret += to[2];
//        }else{
//            ret += 2 * to[2];
//        }
//        return ret;
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int[] from = new int[3];
//            for(int i = 0;i < 3;i++){
//                from[i] = sc.nextInt();
//            }
//            int[] to = new int[3];
//            for(int i = 0;i < 3;i++){
//                to[i] = sc.nextInt();
//            }
//            System.out.println(money(from,to));
//        }
//    }
//}

// 分解因数
//public class Main{
//    public static void main(String[] args) {
//        Scanner input = new Scanner(System.in);
//        while (input.hasNext()) {
//            int n = input.nextInt();
//            if (isPrimer(n)) {
//                System.out.println(n + " = " + n);
//                continue;
//            }
//            System.out.print(n + " = ");
//            int i = 2, len = n / 2;
//            for (; i <= len; ) {
//                if (n % i == 0) {
//                    System.out.print(i);
//                    n /= i;
//                    if (n / i != 0) System.out.print(" * ");
//                    else break;
//                } else i++;
//            }
//            System.out.println();
//        }
//    }
//
//    public static boolean isPrimer(int n) {
//        for (int i = 2; i <= Math.pow(n, 0.5); i++) {
//            if (n % i == 0) return false;
//        }
//        return true;
//    }
//}

// 美国节日
//import java.util.*;
//import java.text.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int year = sc.nextInt();
//            int[] month = new int[]{1,2,5,9,11};
//            int len = month.length;
//            int wek[] = new int[len];
////             创建 Calendar 对象
//            Calendar cal = Calendar.getInstance();
//            try{
////                 对 Calendar 设置时间的方法
////                 设置传入的时间格式
//                SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-M-d");
//                for(int i = 0;i < len;i++){
////                     指定一个日期
//                    Date date = dateFormat.parse(year+"-"+month[i]+"-1");
////                     对 calendar 设置为 date 所指定的日期
//                    cal.setTime(date);
////                     每月1号为位于星期几
//                    int week = cal.get(Calendar.DAY_OF_WEEK)-1;
//                    if(week == 0) week = 7;
//                    wek[i] = week;
//                }
//            } catch(Exception e){
//                e.printStackTrace();
//            }
//            System.out.println(year + "-01-01");
////             1月的第三个星期一
//            int january = wek[0];
//            int rs = 0;
//            String strRs ="";
//            if(january == 1){
//                rs = 2 * 7 + 1;
//            }else{
//                rs = 3 * 7 - (january -1)+1;
//            }
//            strRs = rs/10 == 0 ?"0"+rs : String.valueOf(rs);
//            System.out.println(year+"-01-"+ strRs);
////             2月的第三个星期一
//            int february = wek[1];
//            if(february == 1){
//                rs = 2 * 7 +1;
//            }else{
//                rs = 3 * 7 - (february-1)+1;
//            }
//            strRs = rs/10 == 0 ?"0"+rs : String.valueOf(rs);
//            System.out.println(year+"-02-"+ strRs);
////             5月的最后一个星期一
//            int may = wek[2];
//            if(may >= 6){
////                 第五个星期一
//                rs = may == 6 ? 31 : 30;
//            }else{
////                 第4个星期一
//                rs = 4 * 7 - (may-1)+1;
//            }
//            strRs = rs/10 == 0 ?"0"+rs : String.valueOf(rs);
//            System.out.println(year+"-05-"+ strRs);
//            System.out.println(year+"-07-04");
////             9月的第一个星期一
//            int september = wek[3];
//            if(september == 1){
//                rs = 1;
//            }else{
//                rs = 1 * 7 - (september-1)+1;
//            }
//            strRs = rs/10 == 0 ?"0"+rs : String.valueOf(rs);
//            System.out.println(year+"-09-"+ strRs);
////             11 月的第四个星期四
//            int november =wek[4];
//            rs = 4 * 7 - (november - 1) + 4;
//            strRs = rs/10 == 0 ?"0"+rs : String.valueOf(rs);
//            System.out.println(year+"-11-"+ strRs);
//            System.out.println(year+"-12-25");
//            System.out.println();
//        }
//    }
//}


//因子个数
//public class Main{
//    public static void main(String[] args){
//        Scanner s = new Scanner(System.in);
//        while(s.hasNext()){
//            int n = s.nextInt();
//            int ret = 0;
//            // 从2到n的平方根开始遍历因子
//            for(int i = 2; i <= Math.sqrt(n); i++){
//                // 碰到能整除的因子
//                if(n % i == 0){
//                    // 不断地除这个因子直到不能整除为止，因子数加一，进入下一次循环
//                    while(n % i == 0){
//                        n = n / i;
//                    }
//                    ret++;
//                }
//            }
//            // 当循环结束n不为1，即没能整除，说明此时的n也是一个因子
//            if(n != 1) ret++;
//            System.out.println(ret);
//        }
//    }
//}


//最难的问题
//public class Main{
//
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String s = sc.nextLine();
//            char[] chars = s.toCharArray();
//            StringBuffer sb = new StringBuffer();
//            for(int i = 0; i < s.length(); i++){
//                char c = chars[i];
//                if(c >= 'A' && c < 'F'){
//                    sb.append((char)(c + 21));
//                }else if(c > 'E' && c <= 'Z'){
//                    sb.append((char)(c - 5));
//                }else{
//                    sb.append(c);
//                }
//            }
//            System.out.println(sb.toString());
//        }
//    }
//}

//有假币
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n == 0){
//                return;
//            }else if(n == 1){
//                System.out.println(0);
//            }else if(n == 2 || n == 3){
//                System.out.println(1);
//            }else{
//                int count = 1;
//                while(n > 3){
//                    if(n % 3 == 0){
//                        n /= 3;
//                    }else{
//                        n = n/3 +1;
//                    }
//                    count++;
//                }
//                System.out.println(count);
//            }
//
//        }
//        sc.close();
//    }
//}

//求正数数组的最小不可能组成和
//public class Solution {
//	/**
//	 *	正数数组中的最小不可组成和
//	 *	输入：正数数组arr
//	 *	返回：正数数组中的最小不可组成和
//	 */
//	public int getFirstUnFormedNum(int[] arr) {
//        Arrays.sort(arr);
//        int min = arr[0];
//        int max = arr[0];
//        ArrayList<Integer> result = new ArrayList<>();
//        getNumber(arr,result,0,0);
//        for(int i = 1;i < arr.length;i++){
//            max += arr[i];
//        }
//        for(int i = min + 1;i < max;i++){
//            if(!result.contains(i)){
//                return i;
//            }
//        }
//        return max + 1;
//	}
//    public  void getNumber(int[] arr,ArrayList<Integer> result,int pos,int sum){
//        if(pos == arr.length){
//            return;
//        }
//        for(int i = pos;i < arr.length;i++){
//            sum += arr[i];
//            result.add(sum);
//            getNumber(arr,result,i+1,sum);
//            sum -= arr[i];
//        }
//    }
//}

//猴子分桃
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            long n = sc.nextLong();
//            if(n == 0){
//                break;
//            }
//            long a = (long)Math.pow(5,n);
//            long b = (long)Math.pow(4,n);
//            System.out.println((a-4)+" "+ (b-4+n));
//        }
//        sc.close();
//    }
//}


// 三角形
//import java.util.*;
//import java.math.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            BigInteger a = sc.nextBigInteger();
//            BigInteger b = sc.nextBigInteger();
//            BigInteger c = sc.nextBigInteger();
//            boolean flag = true;
//            if(a.add(b).compareTo(c)<= 0) flag = false;
//            if(a.add(c).compareTo(b)<= 0) flag = false;
//            if(c.add(b).compareTo(a)<= 0) flag = false;
//            if(flag) System.out.println("Yes");
//            else  System.out.println("No");
//        }
//    }
//}

//不用做加减乘除  做加法
//public class Solution {
//    public int Add(int num1,int num2) {
//        while(num2 != 0){
//            int tmp = num2^num1;
//            num2 = (num1 & num2) << 1;
//            num1 = tmp;
//        }
//        return num1;
//    }
//}

//快到碗里来
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            Double n = sc.nextDouble();
//            Double r = sc.nextDouble();
//            if(2*3.14*r > n){
//                System.out.println("Yes");
//            }else{
//                System.out.println("No");
//            }
//        }
//        sc.close();
//    }
//}

//跳台扩展问题
//public class Solution {
//    public int jumpFloorII(int target) {
//        int a = 1;
//        int b = 1;
//        if(target == 1){
//            return target;
//        }
//        while(target-- > 1){
//            b = 2 * a;
//            a = b;
//        }
//        return b;
//    }
//}


//数根
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            int num;
//            do{
//                num = 0;
//                for(int i = 0;i < str.length();i++){
//                    num += str.charAt(i) - 48;
//                }
//                str = num + "";
//            }while(num >= 10);
//            System.out.println(num);
//        }
//        sc.close();
//    }
//}

// 星际密码
//public class Main{
//    public static void main(String[] args){
//        int[] fib = new int[10001];
//        fib[0] = 1;
//        fib[1] = 1;
//        for(int i = 2;i < fib.length;i++){
//            fib[i] = (fib[i-1] + fib[i-2])%10000;
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            while(n-- > 0){
//                int x = sc.nextInt();
//                int zero = 4 - String.valueOf(fib[x]).length();
//                while(zero-->0){
//                    System.out.print("0");
//                }
//                System.out.print(fib[x]);
//            }
//            System.out.println();
//        }
//        sc.close();
//    }
//}

//迷宫问题
//public class Main{
//    static List<List<Integer>> lists = new ArrayList<List<Integer>>();
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int m = sc.nextInt();
//            int n = sc.nextInt();
//            int[][] arr = new int[m][n];
//            for(int i = 0;i < m;i++){
//                for(int j = 0;j < n;j++){
//                    arr[i][j] = sc.nextInt();
//                }
//            }
//            int[][] hp = new int[m][n];
//            List<Integer> list = new ArrayList<>();
//            helper(arr,0,0,list,m,n,hp);
//            Collections.sort(lists, new Comparator<List<Integer>>() {
//                public int compare(List<Integer> o1, List<Integer> o2) {
//                    return o1.size()-o2.size();
//                }
//            });//对lists的元素也就是路径长度进行排序
//            list = lists.get(0);
//            for(int i = 0;i <list.size();i++){
//                System.out.println("(" + list.get(i) +","+list.get(++i) + ")");
//            }
//            lists.clear();
//        }
//    }
//    private static void helper(int[][] arr,int m,int n,List<Integer> list,int row,int col,int[][] hp){
//        if(m<0 || n < 0 || m>=row || n >= col || hp[m][n] == 1 || arr[m][n] == 1){}
//        //到达终点
//        else if(m == row-1 && n == col-1){
//            list.add(m);
//            list.add(n);
//            lists.add(new ArrayList<Integer>(list));//得到一条完整路径
//            list.remove(list.size()-1);//将list的终点坐标清除，回溯法的核心就是办完事（达到目标）一定要完全还原之前的状态
//            list.remove(list.size()-1);//这里的list是引用传递，所以不清除的话会一直带着终点坐标
//        }else{
//            list.add(m);
//            list.add(n);
//            hp[m][n] =1;
//            helper(arr,m+1,n,list,row,col,hp);
//            helper(arr,m,n+1,list,row,col,hp);
//            helper(arr,m-1,n,list,row,col,hp);
//            helper(arr,m,n-1,list,row,col,hp);
//            hp[m][n] = 0;//回溯
//            list.remove(list.size()-1);//回溯
//            list.remove(list.size()-1);//回溯
//        }
//    }
//}

//年终奖
//public class Bonus {
//    public int getMost(int[][] board) {
//        int[][] dp = new int[6][6];
//        dp[0][0] = board[0][0];
//        for(int i = 1;i < 6;i++){
//            dp[0][i] = board[0][i]+dp[0][i-1];
//        }
//        for(int i = 1;i < 6;i++){
//            dp[i][0] = board[i][0]+dp[i-1][0];
//        }
//        for(int i = 1;i < 6;i++){
//            for(int j = 1;j < 6;j++){
//                if(dp[i-1][j]>dp[i][j-1]){
//                    dp[i][j] = board[i][j] + dp[i-1][j];
//                }else{
//                    dp[i][j] = board[i][j]+dp[i][j-1];
//                }
//            }
//        }
//        return dp[5][5];
//    }
//}


//计算字符串的编辑距离 - day23
//public class Main {
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while(in.hasNext()){
//            String strA = in.next();
//            String strB = in.next();
//            int ic = 1;
//            int dc = 1;
//            int rc = 1;
//            int cost = strEditCost(strA, strB, ic, dc, rc);
//            System.out.println(cost);
//        }
//        in.close();
//    }
//    public static int strEditCost(String strA, String strB, int ic, int dc, int rc){
//        /* 字符串之间的距离，编辑距离，将strA编辑成strB所需的最小代价
//         * 编辑操作包括插入一个字符、删除一个字符、替换一个字符
//         * 分别对应的代价是ic、dc、rc，insert cost、delete cost、replace cost
//         * strA[x-1]代表strA的第x个字符，注意下标是从0开始的,strA[y-1]代表strA的第y个字符
//         * 定义一个代价矩阵为(N+1)*(M+1)，M N 表示strA strB的长度
//         * dp[x][y]表示strA的前x个字符串编辑成 strB的前y个字符所花费的代价
//         * dp[x][y]是下面几种值的最小值：
//             * 1、dp[x][y] = dp[x-1][y] + dc
//             * dp[x-1][y]将strA的前x-1个字符编辑成strB的前y个字符的代价已知，
//             * 那么将strA的前x个字符编辑成strB的前y个字符的代价dp[x][y]就是dp[x-1][y] + dc
//             * 相当于strA的前x-1个字符编辑成strB的前y个字符，现在变成了strA的前x个字符，增加了一个字符，要加上删除代价
//             * 2、dp[x][y] = dp[x][y-1] + ic
//             * dp[x][y-1]将strA的前x个字符编辑成strB的前y-1个字符的代价已知，
//             * 现在变为strB的前y个字符，相应的在strA前x个操作代价的基础上插入一个字符
//             * 3、dp[x][y] = dp[x-1][y-1]
//             * dp[x-1][y-1]将strA的前x-1个字符编辑成strB的前y-1个字符的代价已知，
//             * strA的第x个字符和strB的第y个字符相同，strA[x-1] == strB[y-1]，没有引入操作
//             * 4、dp[x][y] = dp[x-1][y-1] + rc
//             * strA的第x个字符和strB的第y个字符不相同，strA[x-1] ！= strB[y-1]，
//             * 在strA的前x-1个字符编辑成strB的前y-1个字符的代价已知的情况下，
//             * 计算在strA的前x字符编辑成strB的前y个字符的代价需要加上替换一个字符的代价
//         * */
//        int m = strA.length();
//        int n = strB.length();
//        int[][] dp = new int[m + 1][n + 1];
//        for (int i = 1; i <= n; i++) dp[0][i] = i*ic;
//        for (int i = 1; i <= m; i++) dp[i][0] = i*dc;
//        for (int x = 1; x <= m; x++) {
//            for (int y = 1; y <= n; y++) {
//                int cost1 = dp[x-1][y] + dc;
//                int cost2 = dp[x][y-1] + ic;
//                int cost3 = 0;
//                if(strA.charAt(x-1) == strB.charAt(y-1))
//                    cost3 = dp[x-1][y-1];
//                else
//                    cost3 = dp[x-1][y-1] + rc;
//                dp[x][y] = Math.min(cost1, cost2);
//                dp[x][y] = Math.min(dp[x][y], cost3);
//            }
//        }
//        return dp[m][n];
//    }
//}

//微信红包
//public class Gift {
//    public int getValue(int[] gifts, int n) {
//     int ret = gifts[0], j= 1;
//       for(int i = 1;i<n;i++){
//            if(gifts[i]==ret){
//                j++;
//            }else{
//                j--;
//            }
//            if(j==0){
//                ret=gifts[i];
//                j =1;
//            }
//        }
//
//        if(j>1){
//            return ret;
//        }
//        return 0;
//    }
//}


//第一个只出现一次的字符
//public class Main{
//    public static void main(String[] args){
//        Scanner sc= new Scanner(System.in);
//        HashMap<Character,Integer> map = new HashMap<>();
//        while(sc.hasNext()){
//            String str= sc.nextLine();
//            for(int i = 0;i < str.length();i++){
//                char ch = str.charAt(i);
//                map.put(ch,map.getOrDefault(ch,0)+1);
//            }
//            for(int i = 0;i < str.length();i++){
//                char ch = str.charAt(i);
//                if(map.get(ch) == 1){
//                    System.out.println(ch);
//                    return;
//                }
//            }
//            System.out.println(-1);
//        }
//        sc.close();
//    }
//}


// 小易的升级之路
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int a = sc.nextInt();
//            int[] monster = new int[n];
//            for(int i = 0;i<n;i++){
//                monster[i] = sc.nextInt();
//                if(a > monster[i]){
//                    a += monster[i];
//                }else{
//                    a += commonDivisor(a,monster[i]);
//                }
//            }
//            System.out.println(a);
//        }
//        sc.close();
//    }
//    private static int commonDivisor(int a,int monsterIndex){
//        if(monsterIndex % a == 0){
//            return a;
//        }else{
//            return commonDivisor(monsterIndex%a,a);
//        }
//    }
//}


//MP3 光标位置
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String str = sc.next();
//            int top = 1,index = 1;
//            for(int i = 0;i< str.length();i++){
//                if(str.charAt(i) == 'U'){
//                    if(top == index){
//                        top = top == 1 ? n - 3: top-1;
//                    }
//                    index = index == 1 ? n : index-1;
//                }else if(str.charAt(i) == 'D'){
//                    if(top + 3 == index){
//                        top = index == n ? 1 :top+1;
//                    }
//                    index = index == n ? 1 :index + 1;
//                }
//            }
//            if(n < 4){
//                top = 1;
//             }
//             for(int i = 0;i < 3 && i < n -1;i++){
//                 System.out.print(top + i + " ");
//             }
//             System.out.println(top + (4 > n ? n - 1:3));
//             System.out.println(index);
//        }
//        sc.close();
//    }
//}


//洗牌
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int group = sc.nextInt();
//            while(group-->0){
//                int n = sc.nextInt();
//                int k = sc.nextInt();
//                int[] res = new int[2*n];
//                for(int i = 0;i<2*n;i++){
//                    int tmp = i + 1;
//                    for(int j = 0;j<k;j++){
//                        if(tmp <= n){
//                            tmp = 2 * tmp -1;
//                        }else{
//                            tmp = 2*(tmp - n);
//                        }
//                    }
//                    res[tmp - 1] = sc.nextInt();
//                }
//                for(int i=0;i<2*n;i++){
//                    System.out.print(res[i]+" ");
//                }
//                 System.out.println();
//            }
//        }
//        sc.close();
//    }
//}


//公共子串计算
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str1 =sc.nextLine();
//            String str2= sc.nextLine();
//            isNum(str1,str2);
//        }
//        sc.close();
//    }
//    private static void isNum(String p,String s){
//        String longStr = p.length() > s.length()? p:s;
//        String shortStr = p.length() > s.length() ? s:p;
//        int longLen = longStr.length();
//        int shortLen=shortStr.length();
//        int maxlen = 0;
//        for(int i = 0;i < shortLen;i++){
//            if(shortLen - i + 1 <= maxlen){
//                break;
//            }
//            for(int j = i,k = shortLen;k>j;k--){
//                String sub = shortStr.substring(j,k);
//                if(sub.length()>maxlen && longStr.contains(sub)){
//                    maxlen = sub.length();
//                    break;
//                }
//            }
//        }
//        System.out.println(maxlen);
//    }
//}


//字符串反转
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            for(int i = str.length()-1;i>=0;i--){
//                System.out.print(str.charAt(i));
//            }
//             System.out.println();
//        }
//        sc.close();
//    }
//}


//查找两个字符串a,b中的最长公共子串
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str1 = sc.nextLine();
//            String str2 = sc.nextLine();
//            longString(str1,str2);
//        }
//        sc.close();
//    }
//    private static void longString(String s1,String s2){
//        String longStr = s1.length() > s2.length() ? s1 :s2;
//        String shortStr = s1.length() > s2.length() ? s2 :s1;
//        int longLen = longStr.length();
//        int shortLen = shortStr.length();
//        int maxLen = 0,start = 0;
//        for(int i = 0;i<shortStr.length();i++){
//            if(shortLen - i + 1 <= maxLen ){
//                break;
//            }
//            for(int j = i,k = shortLen;k>j;k--){
//                String sub = shortStr.substring(j,k);
//                if(longStr.contains(sub) && sub.length() > maxLen){
//                    maxLen = sub.length();
//                    start = j;
//                    break;
//                }
//            }
//        }
//        System.out.println(shortStr.substring(start,start + maxLen));
//    }
//}

//汽水瓶
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n == 0){
//                System.out.println();
//            }else{
//                System.out.println(n/2);
//            }
//        }
//        sc.close();
//    }
//}

//字符串通配符
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String regular = sc.nextLine().toUpperCase();
//            String s2 = sc.nextLine().toUpperCase();
//            System.out.println(isMatch(regular,s2));
//        }
//        sc.close();
//    }
//    public static boolean isMatch(String s1,String s2){
//        int m = s2.length();
//        int n = s1.length();
//
//        boolean[][] dp = new boolean[m+1][n+1];
//        dp[0][0] = true;
//        for(int i = 1;i <= n;i++){
//            if(s1.charAt(i-1) == '*'){
//                dp[0][i] = true;
//            }else{
//                break;
//            }
//        }
//        for(int i =1;i<=m;i++){
//            boolean f = false,f2 = false;
//            for(int j = 1;j <= n;j++){
//                if(!Character.isLetter(s2.charAt(i-1)) && !Character.isDigit(s2.charAt(i-1))){
//                    if(s2.charAt(i-1) == s1.charAt(j-1)){
//                        f2 = true;
//                        f = false;
//                    }else if(!f2){
//                        f = true;
//                    }
//                }
//                if(s1.charAt(j-1) == '*'){
//                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
//                }else if(s1.charAt(j-1) == '?' || s2.charAt(i-1) == s1.charAt(j-1)){
//                    dp[i][j] = dp[i-1][j-1];
//                }
//            }
//            if(f) return false;
//        }
//        return dp[m][n];
//    }
//}

//统计每个月兔子的总数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            System.out.println(getNumber(n));
//        }
//        sc.close();
//    }
//    private static int getNumber(int months){
//        if(months == 1 || months == 2){
//            return 1;
//        }
//        int tempOld = 1;
//        int tempNew = 1;
//        int month1 = 1;
//        int month2 = 0;
//        for(int i = 4;i <= months;i++){
//            tempOld += month2;
//            month2 = month1;
//            month1 = tempOld;
//            tempNew = month1+month2;
//        }
//        return tempNew + tempOld;
//    }
//}

//杨辉三角的变形
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n <= 2){
//                System.out.println(-1);
//            }else if(n%2 == 1){
//                System.out.println(2);
//            }else{
//                if(n % 4 == 0){
//                    System.out.println(3);
//                }else{
//                    System.out.println(4);
//                }
//            }
//        }
//        sc.close();
//    }
//}


//扑克牌大小
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        String[] left,right;
//        String[] line;
//        String outString,nextLine;
//        while(sc.hasNext()){
//            nextLine = sc.nextLine();
//            if(nextLine.contains("joker JOKER")){
//                outString = "joker JOKER";
//            }else{
//                line = nextLine.split("-");
//                left = line[0].split(" ");
//                right = line[1].split(" ");
//                if(left.length == 4 && right.length!= 4){
//                    outString = line[0];
//                }else if(left.length != 4 && right.length == 4){
//                    outString = line[1];
//                }else if(left.length == right.length){
//                    if(count(left[0]) > count(right[0])){
//                        outString = line[0];
//                    }else{
//                        outString = line[1];
//                    }
//                }else{
//                    outString = "ERROR";
//                }
//            }
//            System.out.println(outString);
//        }
//    }
//    private static int count(String sub){
//        return "345678910JQKAjokerJOKER".indexOf(sub);
//    }
//}

//完全数计算
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int count = 0;
//            for(int i = 2;i <= n;i++){
//                if(perfect(i)){
//                    count++;
//                }
//            }
//            System.out.println(count);
//        }
//    }
//    private static boolean perfect(int n){
//        int sum = 0;
//        for(int i = 2;i < n;i++){
//            if(n % i == 0){
//                sum += i;
//            }
//        }
//        if(sum + 1 == n){
//            return true;
//        }
//        return false;
//    }
//}

//手套
//public class Gloves {
//    public int findMinimum(int n, int[] left, int[] right) {
//        // write code here
//        int sum = 0;
//        List<Integer> leftList = new ArrayList<>();
//        List<Integer> rightList = new ArrayList<>();
//        for(int i = 0;i < n;i++){
//            if(left[i] == 0 && right[i] != 0   ||  left[i] != 0 && right[i] == 0){
//                sum += left[i] + right[i];
//            }else if(left[i] != 0 && right[i] != 0){
//                leftList.add(left[i]);
//                rightList.add(right[i]);
//            }
//        }
//        Collections.sort(leftList);
//        Collections.sort(rightList);
//        int sum1 = 0,sum2 =0;
//        for(int i = leftList.size()-1;i>0;i--){
//            sum1 += leftList.get(i);
//        }
//        for(int i =  rightList.size()-1;i > 0;i--){
//            sum2 += rightList.get(i);
//        }
//        return Math.min(sum2,sum1) + 2 + sum;
//    }
//}

//查找输入整数二进制中 1 的个数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String str = Integer.toBinaryString(n);
//            int count =0;
//            for(int i = 0;i < str.length();i++){
//                if(str.charAt(i) == '1'){
//                    count++;
//                }
//            }
//            System.out.println(count);
//        }
//        sc.close();
//    }
//}

// 幸运的袋子
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int[] balls = new int[n];
//            for(int i = 0;i < n;i++){
//                balls[i] = sc.nextInt();
//            }
//            Arrays.sort(balls);
//            int ret = lucky(balls,0,0,1);
//            System.out.println(ret);
//        }
//        sc.close();
//    }
//    private static int lucky(int[] balls,int index,long sum,long product ){
//        int count =0;
//        for(int i = index;i < balls.length;i++){
//            int num = balls[i];
//            sum += num;
//            product *= num;
//            if( sum > product){
//                count += 1 + lucky(balls,i+1,sum,product);
//            }else if(num == 1){
//                count +=  lucky(balls,i+1,sum,product);
//            }else{
//                break;
//            }
//            sum -= num;
//            product /= num;
//            while(i < balls.length-1 && balls[i] == balls[i+1]){
//                i++;
//            }
//        }
//        return count;
//    }
//}

//计算日期到天数转换
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int year = sc.nextInt();
//            int month = sc.nextInt();
//            int day = sc.nextInt();
//            int[] monthDay =  {31,28,31,30,31,30,31,31,30,31,30,31};
//            int sumday = 0;
//            for(int i = 0;i < month-1;i++){
//                sumday += monthDay[i];
//            }
//            sumday += day;
//            if(month>2 && isLeap(year)){
//                sumday++;
//            }
//            System.out.println(sumday);
//        }
//        sc.close();
//    }
//    private static boolean isLeap(int year){
//        if(year % 400 == 0 || year % 4 == 0 && year % 100 != 0){
//            return true;
//        }
//        return false;
//    }
//}


//跳石板
//public class Main{
//
//    public static void main(String[] args) {
//
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()) {
//            int n = scanner.nextInt();
//            int m = scanner.nextInt();
//            System.out.println(leastJumpTime(n, m));
//        }
//    }
//
//    // 思想：动态规划
//    public static int leastJumpTime(int n, int m) {
//        if (m == n) {
//            return 0;
//        }
//        int steps = m - n + 1;// 算上了起点和终点
//        int[] dp = new int[steps];// 规划的量：到达 每个位置需要的最小步数
//        dp[0] = 0; // 起点
//        for (int i = 1; i < steps; i++) {
//            dp[i] = Integer.MAX_VALUE; // 初始化 表示后续位置都不能到达
//        }
//        for (int i = 0; i < steps; i++) {
//            // 0对应n石板 ；steps - 1 = m-n对应m石板
//            if (dp[i] == Integer.MAX_VALUE) { // 该位置不能像前走
//                dp[i] = 0;
//                continue;
//            }
//            ArrayList<Integer> list = getAppNums(i + n); // i+n才是石板号
//            for (int j = 0; j < list.size(); j++) {
//                int x = list.get(j);
//                if (i + n + x <= m) {
//                    dp[i + x] = Math.min(dp[i + x], dp[i] + 1);
//                }
//            }
//        }
//        if (dp[steps - 1] == 0) {
//            return -1;
//        } else {
//            return dp[steps - 1];
//        }
//    }
//
//    // 求因数 时间复杂度较低
//    public static ArrayList<Integer> getAppNums(int n) {
//        ArrayList<Integer> list = new ArrayList<Integer>();
//        for (int i = 2; i <= Math.sqrt(n); i++) {
//            if (n % i == 0) {
//                list.add(i);
//                if (n / i != i) {
//                    list.add(n / i);
//                }
//            }
//        }
//        return list;
//    }
//}

// 参数解析
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String str = sc.nextLine();
//            StringBuffer sb = new StringBuffer();
//            int count = 0;
//            int quota = 0;
//            for(int i = 0;i<str.length();i++){
//                char ch = str.charAt(i);
//                if(ch == '\"'){
//                    quota++;
//                }else if(ch != ' '){
//                    sb.append(ch);
//
//                }else if(quota % 2 == 0){
//                    sb.append("\n");
//                     count++;
//                }else{
//                    sb.append(' ');
//                }
//            }
//            System.out.println(count+1);
//            System.out.println(sb.toString());
//        }
//        sc.close();
//    }
//}

//查找组成一个偶数最接近的两个素数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int n = sc.nextInt();
//            for(int i = n/2;i>=2;i--){
//                if(isPrime(i) && isPrime(n-i)){
//                    System.out.println(i);
//                    System.out.println(n-i);
//                    break;
//                }
//            }
//        }
//        sc.close();
//    }
//    public static boolean isPrime(int m){
//        for(int i = 2;i<m;i++){
//            if(m%i == 0){
//                return false;
//            }
//        }
//        return true;
//    }
//}

//二进制插入
//public class BinInsert {
//    public int binInsert(int n, int m, int j, int i) {
//        return n | (m<<j);
//    }
//}

//求最大连续bit数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc=new Scanner(System.in);
//        while (sc.hasNext()){
//            int n=sc.nextInt();
//            String s=Integer.toBinaryString(n);
//            int max=0;
//            String[] str=s.split("0");
//            for(int i=0;i<str.length;i++){
//                if(str[i].length()>max){
//                    max=str[i].length();
//                }
//            }
//            System.out.println(max);
//        }
//        sc.close();
//    }
//}

// 根据两个节点的编号求最近公共祖先的编号
//public class LCA {
//    public int getLCA(int a, int b) {
//        while(a!=b){
//            if(a>b){
//                a /= 2;
//            }else{
//                b/=2;
//            }
//        }
//        return a;
//    }
//
//}

// 密码强度等级
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String str = sc.nextLine();
//            int sum = 0;
//            int len = str.length();
//            if(len <= 4){
//                sum+=5;
//            }else if(len>4 && len < 8){
//                sum+=10;
//            }else if(len >7){
//                sum+=25;
//            }
//            boolean flaglowerCase = false;
//            boolean flagUpperCase = false;
//            boolean flagDigit = false;
//            boolean flagSymbol = false;
//            int digitCount = 0;
//            int symbolCount = 0;
//            for(int i = 0;i < len;i++){
//                char ch = str.charAt(i);
//                if(!Character.isDigit(ch)){
//                    if(ch >= 'a' && ch <= 'z'){
//                        flaglowerCase = true;
//                    }else if(ch >= 'A' && ch <='Z'){
//                        flagUpperCase = true;
//                    }else{
//                        flagSymbol = true;
//                        symbolCount++;
//                    }
//                }else{
//                    flagDigit = true;
//                    digitCount++;
//                }
//            }
//            if((flaglowerCase && (!flagUpperCase)) || (flagUpperCase && (!flaglowerCase))){
//                sum+=10;
//            }else if(flaglowerCase && flagUpperCase){
//                sum +=20;
//            }
//            if(flagDigit){
//                if(digitCount == 1){
//                    sum +=10;
//                }else if(digitCount > 1){
//                    sum += 20;
//                }
//            }
//            if(flagSymbol){
//                if(symbolCount ==1){
//                    sum += 10;
//                }else if(symbolCount >1){
//                    sum += 25;
//                }
//            }
//            if(flagSymbol && flagUpperCase && flaglowerCase  && flagDigit){
//                sum +=5;
//            }else if((flagUpperCase && flagDigit && flagSymbol) || (flaglowerCase && flagDigit && flagSymbol) ){
//                sum+=3;
//            }else if((flagUpperCase && flagDigit) || (flagDigit && flaglowerCase)){
//                sum +=2;
//            }
//                if(sum >= 90){
//                   System.out.println("VERY_SECURE");
//                }else if(sum>=80 ){
//                    System.out.println("SECURE");
//                }else if(sum>=70 ){
//                    System.out.println("VERY_STRONG");
//                }else if(sum>=60) {
//                    System.out.println("STRONG");
//                }else if(sum>=50 ){
//                    System.out.println("AVERAGE");
//                }else if(sum>=25 ){
//                    System.out.println("WEAK");
//                }else if(sum>=0 ){
//                    System.out.println("VERY_WEAK");
//                }
//        }
//    }
//}


// 井字棋
//public class Board {
//    public boolean checkWon(int[][] board) {
//        for(int i = 0;i<3;i++){
//            if((board[i][0] == board[i][1] && board[i][1] == board[i][2]) && board[i][0] == 1 ){
//                return true;
//            }
//        }
//        if((board[0][0] == board[1][1] && board[1][1] == board[2][2]) && board[0][0] == 1){
//            return true;
//        }
//        if((board[0][2] == board[1][1] && board[1][1] == board[2][0]) && board[1][1] == 1){
//            return true;
//        }
//        return false;
//    }
//}

//走方格的方案数
//public class Main{
//    public static void main(String[] str){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int m = sc.nextInt(),n = sc.nextInt();
//            System.out.println(recursion(0,0,m,n));
//        }
//    }
//    public static int recursion(int i,int j,int m,int n){
//        if(i == m || j == n){
//            return 1;
//        }
//        return recursion(i + 1,j,m,n) + recursion(i,j+1,m,n);
//    }
//}

//另类算法
//public class UnusualAdd {
//    public int addAB(int A, int B) {
//        // write code here
//        while(B!=0){
//            int tmp = A^B;
//            B = (A&B)<<1;
//            A = tmp;
//        }
//        return A;
//    }
//}


// 求两个数的最小公倍数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc= new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int a = sc.nextInt(),b = sc.nextInt();
//            int result = a * b / gcd(a,b);
//            System.out.println(result);
//        }
//    }
//    public static int gcd(int a,int b){
//        return b > 0 ? gcd(b,a%b):a;
//    }
//}



// 两种排序
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            // 获取字符串个数
//            int n = Integer.parseInt(sc.nextLine());
//            // 创建一个顺序表来存储接下来输入的字符串
//            List<String> list = new ArrayList<>();
//            for(int i = 0;i < n;i++){
//                list.add(sc.nextLine());
//            }
//            // “拷贝”一份 list 顺序表
//            List<String> p = new ArrayList<>(list);
//            Collections.sort(p);// 排序：默认按照字典序进行排序
//            boolean a = p.equals(list);// 如果 排序结果与 为排序结果一样，则为true;，反之为 false
//            boolean b = true;// 默认是按照长度排序的
//
//            // 遍历 list 顺序表
//            for(int i = 0;i< list.size()-1;i++){
//                //判断 是否是按照长度排序的
//                if(list.get(i).length() > list.get(i+1).length()){
//                    b = false;
//                }
//            }
//            if(a && b){
//                System.out.println("both");
//                return;
//            }
//            if(a){
//                System.out.println("lexicographically");
//                return;
//            }
//            if(b){
//                System.out.println("lengths");
//                return;
//            }
//            System.out.println("none");
//        }
//    }
//}

//合法括号序列判断
//public class Parenthesis {
//    public boolean chkParenthesis(String A, int n) {
//        // write code here
//        Stack<Character> stack = new Stack<>();
//        for(int i = 0; i < n;i++){
//            char ch = A.charAt(i);
//            if(ch == '('){
//                stack.push(ch);
//            }else{
//                if(ch == ')' && !stack.isEmpty()){
//                   stack.pop();
//                }else{
//                    return false;
//                }
//
//            }
//        }
//        return stack.isEmpty();
//    }
//}

// 输入一个数N，求最少多少步可以变为 fibonacci 数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int n = sc.nextInt();
//            System.out.println(fibonacci(n));
//        }
//    }
//    public static int fibonacci(int n){
//        int a = 0;
//        int b = 1;
//        int c = 1;
//        while(c < n){
//            a = b;
//            b = c;
//            c=a+b;
//        }
//        return Math.min((c-n) , (n - b));
//    }
//}


// 不要二
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int row = sc.nextInt(),rank=sc.nextInt(),result = 0;
//            int[][] arr = new int[row][rank];
//            for(int i = 0;i < row;i++){
//                for(int j=0;j<rank;j++){
//                    if(arr[i][j] == 0){
//                        arr[i][j] = 1;
//                        result++;
//                        if(i+2 < row){
//                            arr[i+2][j] = 2;
//                        }
//                        if(j + 2 < rank){
//                            arr[i][j+2] = 2;
//                        }
//                    }
//                }
//            }
//            System.out.println(result);
//        }
//    }
//}


// 统计回文
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String A = sc.nextLine();
//            String B = sc.nextLine();
//            int  m = 0;
//            for(int i =0;i < A.length()+1;i++){
//                String str = A.substring(0,i) + B + A.substring(i,A.length());
//                StringBuffer sb = new StringBuffer(str);
//                if(sb.reverse().toString().equals(str)){
//                    m++;
//                }
//            }
//            System.out.println(m);
//        }
//    }
//}

//一个数组有 N 个元素，求连续子数组的最大和
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int n = sc.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0;i < n;i++){
//                arr[i] = sc.nextInt();
//            }
//            int result = arr[0];
//            int sum = arr[0];
//            for(int i = 1;i < n;i++){
//                sum = Math.max(sum,0) + arr[i];
//                if(sum > result){
//                    result = sum;
//                }
//            }
//            System.out.println(result);
//        }
//        sc.close();
//    }
//}



// 算法题
// public static void main(String[] args){
//    Scanner sc = new Scanner(System.in);
//    while(sc.hasNextInt()){
//        int[] nums = new int[4];
//        for(int i =0;i < 4;i++) nums[i] = sc.nextInt();
//        if((nums[o] + num[1]) != (nums[2] - num[3])) System.out.println("No");
//        else{
//            int a = (nums[0] + nums[2]) / 2;
//            int b = (nums[1] + nums[3]) / 2;
//             System.out.println( a + " " + b + “ ” + （num[3] - b）);
//        }
//    }
// }

//面试必考真题-算法篇：给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数。
//public class Solution {
//    /**
//     * 进制转换
//     * @param M int整型 给定整数
//     * @param N int整型 转换到的进制
//     * @return string字符串
//     */
//    public String solve (int M, int N) {
//        // write code here
//        if(M == 0){
//            return "0";
//        }
//        //要考虑 M 为负数的情况
//        boolean flag = true;
//        if(M < 0){
//            M = -M;
//            flag = false;
//        }
//
//        StringBuffer res = new StringBuffer();
//        String hex = "0123456789ABCDEF";
//
//        while(M !=0){
//            res.append(hex.charAt(M%N));
//            M = M / N;
//        }
//        // 字符串反转
//        return flag == true ? res.reverse().toString():"-"+res.reverse().toString();
//    }
//}

//字符串中找出连续最长的数字串字符串中找出连续最长的数字串
// import java.util.*;
// public class·Main{
//     public static void main(String[] args){
//         Scanner sc = new·Scanner(System.in);
//          while(sc.hasNext()){
//              String str=sc.nextLine();
//              String[] s=str.split("[a-z]");
//              string r ="";
//              for(String ·ss:s){
//                  if(ss.contains("  " ))continue;
//                  if(ss.length()>r.length()){
//                      r=SS;
//              }
//          }
//          System. out.println(r);17 ·. ...·.}
//     }
//}


// 牛客排序子序列
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n =  sc.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0; i < n;i++){
//                arr[i] = sc.nextInt();
//            }
//            int result = 1;
//            int flag = 0;//表示位：0表示相等，1表示递增，-1表示递减
//            for(int i = 1;i< n;i++){
//                if(arr[i] >arr[i-1]){
//                    if(flag == 0){
//                        flag = 1;
//                    }else if(flag == -1){
//                        flag = 0;
//                        result++;
//                    }
//                }
//                if(arr[i] < arr[i-1]){
//                    if(flag == 0){
//                        flag = -1;
//                    }else if(flag == 1){
//                        flag = 0;
//                        result++;
//                    }
//                }
//            }
//            System.out.println(result);
//        }
//    }
//}

// 牛客：倒置字符串
//public class Main{
//    public static void main(String[] args){
//        Scanner sc =  new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            String[] arr= str.split(" ");
//            for(int i = arr.length - 1;i>=0;i--){
//                System.out.print(arr[i] + " ");
//            }
//        }
//    }
//}



// LeetCode - 958. 二叉树的完全性检验
//class Solution {
//    public boolean isCompleteTree(TreeNode root) {
//        List<Node> list = new ArrayList<>();
//        list.add(new Node(root,1));
//        int i = 0;
//        while(i <list.size()){
//            Node tmp = list.get(i++);
//            if(tmp.node != null){
//                list.add(new Node(tmp.node.left,tmp.code * 2));
//                list.add(new Node(tmp.node.right,tmp.code * 2 + 1));
//            }
//        }
//        return list.get(i-1).code == list.size();
//    }
//
//    class Node{
//        public TreeNode node;
//        public int code;
//        public Node(TreeNode node,int code){
//            this.node  = node;
//            this.code = code;
//        }
//    }
//}



//LeetCode - 387. 字符串中的第一个唯一字符
// 数据结构 HashMap
//class Solution {
//    public int firstUniqChar(String s) {
//        Map<Character,Integer> map =  new HashMap<>();
//        for(int i = 0;i < s.length();i++){
//            char ch = s.charAt(i);
//            map.put(ch,map.getOrDefault(ch,0)+1);
//            // if(map.containsKey(ch)){
//            //     int val = map.get(ch);
//            //     map.put(ch,val+1);
//            // }else{
//            //     map.put(ch,1);
//            // }
//        }
//        for(int i = 0; i < s.length();i++){
//            char ch = s.charAt(i);
//            if(map.get(ch) == 1){
//                return i;
//            }
//        }
//        return -1;
//    }
//}


// 哈希函数思维
//class Solution {
//    public int firstUniqChar(String s) {
//        int[] array = new int[26];
//        for(int i = 0;i < s.length();i++){
//            array[s.charAt(i) - 'a']++;
//        }
//        for(int i = 0;i < s.length();i++){
//            if(array[s.charAt(i) - 'a'] == 1){
//                return i;
//            }
//        }
//        return -1;
//    }
//}


// LeetCode - 692. 前K个高频单词
//public class Manuscript{
//    public static List<String> topKFrequent(String[] words, int k) {
//        // 1、 统计 每个单词的出现的次数 》》 map
//        HashMap<String,Integer> map = new HashMap<>();
//        for(String s : words){
//            if(map.get(s) == null){
//                map.put(s,1);
//            }else{
//                int val = map.get(s);
//                map.put(s,val+1);
//            }
//        }
//
//        // 第二步 建立一个 大小为 K 的小根堆。
//        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
//            @Override
//            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
//                if(o1.getValue().compareTo(o2.getValue()) == 0){
//                    return o2.getKey().compareTo(o1.getKey());
//                }
//                return o1.getValue() - o2.getValue();
//            }
//        });
//
//
//        // 遍历map，建堆。
//        for (Map.Entry<String,Integer> entry:map.entrySet()) {
//            if(minHeap.size() < k){
//                minHeap.offer(entry);
//            }else {
//                // 说明堆中 已经放满了 K 个元素，需要看堆顶元素的数据 和 当前的数据的大小关系
//                Map.Entry<String,Integer> top = minHeap.peek();
//                //判断频率是否相同，如果相同，比较单词的大小，单词ASCII小 的 入队。
//                if(entry.getValue().compareTo(top.getValue()) == 0 ){
//                    if(top.getKey().compareTo(entry.getKey()) > 0){
//                        minHeap.poll();
//                        minHeap.offer(entry);
//                    }
//                }else{
//                    if(entry.getValue().compareTo(top.getValue()) > 0){
//                        minHeap.poll();
//                        minHeap.offer(entry);
//                    }
//                }
//            }
//        }
//        System.out.println(minHeap);
//        List<String> ret = new ArrayList<>();
//        for(int i = 0;i < k;i++){
//            Map.Entry<String,Integer> top = minHeap.poll();
//            ret.add(top.getKey());
//        }
//        Collections.reverse(ret);
//        return ret;
//    }
//
//    public static void main(String[] args) {
//        String[] worlds = {"i", "love", "leetcode", "i", "love", "coding"};
//        List<String> list = topKFrequent(worlds,3);
//        System.out.println(list);
//    }
//}




// LeetCode - 692. 前K个高频单词
//



//牛客网 - 旧键盘
// HashSet 方法
//import java.util.*;// 导包
//public class Main{
//
//    public static void function(String strExpect,String strActtal){
//        Set<Character> setA = new HashSet<>();
//        // strActtal 先转大写，再转为数组
//        for(char ch : strActtal.toUpperCase().toCharArray()){
//            setA.add(ch);
//        }
//        Set<Character> setP = new HashSet<>();
//          // strExpect 先转大写，再转为数组
//        for(char ch : strExpect.toUpperCase().toCharArray()){
//            if(!setA.contains(ch) && !setP.contains(ch)){
//                System.out.print(ch);
//                setP.add(ch);
//            }
//        }
//    }
//
//
//    public static void main(String[] args){
//        // 循环输入
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String strExpect = sc.nextLine();
//            String strActtal = sc.nextLine();
//            function(strExpect,strActtal);
//        }
//        sc.close();// 资源回收
//    }
//}



//LeetCode - 771. 宝石与石头
//class Solution {
//    public int numJewelsInStones(String jewels, String stones) {
//        Set<Character> set = new HashSet<>();
//        for(int i = 0; i < jewels.length();i++){
//            set.add(jewels.charAt(i));
//        }
//        int result = 0;
//        for(int i = 0; i < stones.length();i++){
//            if(set.contains(stones.charAt(i))){
//                result++;
//            }
//        }
//        return result;
//    }
//}

// LeetCode - 136. 只出现一次的数字
// 异或
//class Solution {
//    public int singleNumber(int[] nums) {
//        int result = nums[0];
//        for(int i = 1;i < nums.length;i++){
//            result ^= nums[i];
//        }
//        return result;
//    }
//}


// HashMap 方法
//class Solution {
//    public int singleNumber(int[] nums) {
//        Map<Integer,Integer> map = new HashMap<>();
//        for(int i : nums){
//            Integer count = map.get(i);
//             count = count == null ? 1 : ++count;
//            map.put(i, count);
//        }
//        for(int i : nums){
//            Integer count = map.get(i);
//            if(count == 1){
//                return i;
//            }
//        }
//        return -1;
//    }
//}

// HashSet 方法
//class Solution {
//    public int singleNumber(int[] nums) {
//        Set<Integer> set = new HashSet<>();
//        for(int i : nums){
//            if(set.contains(i)){
//                set.remove(i);
//            }else{
//                set.add(i);
//            }
//        }
//        int result = 0;
//        for(int i : nums){
//            if( set.contains(i)){
//                result = i;
//            }
//        }
//        return result;
//    }
//}




// LeetCode - 138. 复制带随机指针的链表
// 方法： HashMap 的 映射关系
//class Solution {
//
//    public Node copyRandomList(Node head) {
//        Map<Node,Node> map = new HashMap<>();
//        Node tmp = head;
//        while(tmp!=null){
//            Node node = new Node(tmp.val);
//            map.put(tmp,node);
//            tmp = tmp.next;
//        }
//        tmp = head;
//        while(tmp!=null){
//            map.get(tmp).next = map.get(tmp.next);
//            map.get(tmp).random = map.get(tmp.random);
//            tmp = tmp.next;
//        }
//        return map.get(head);
//    }
//}




// LeetCode - 117. 填充每个节点的下一个右侧节点指针 II
// 方式一： 利用建立好的next，将每一层节点看作是一个链表。
//class Solution {
//    public Node connect(Node root) {
//        if(root == null){
//            return root;
//        }
//        // 将cur 当 一个链表
//        Node cur = root;
//        while(cur!=null){
//            // 在遍历当层的时候，将下一层的节点连接起来。
//            // 为了方便操作，使用了一傀儡节点
//            Node dummy = new Node();
//            // 每一层的起始节点 的 前一个节点。
//            Node  pre = dummy;
//            while( cur != null){// 遍历当前 cur 层的节点
//                if(cur.left != null){
//                    // 如果 cur.left 不为空 pre的下一个节点 就是 cur.left
//                    // 也就说将它们串起来【填充next值】
//                    pre.next = cur.left;
//                    // pre 移动，为下一次链接做准备
//                    pre = pre.next;
//                }
//                if(cur.right != null){
//                    // 如果 cur.right 不为空 pre的下一个节点 就是 cur.right
//                    // 也就说将它们串起来【填充next值】
//                    pre.next = cur.right;
//                    // pre 移动，为下一次链接做准备
//                    pre = pre.next;
//                }
//                // cur 移动，访问这一行的下一个节点。
//                cur =cur.next;
//            }
//            // 前面说到 dummy 是 下一层节点的 起始位置 的 傀儡节点
//            // 它的next指向的节点，就是 cur 下一层的遍历的起始位置
//            cur = dummy.next;
//        }
//        return root;
//    }
//}

// 方法二： 队列
//class Solution {
//    public Node connect(Node root) {
//        if(root == null){
//            return root;
//        }
//        Queue<Node> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            for(int i = 0;i < size;i++){
//                Node tmp = queue.poll();
//                if(i < size -1){
//                    tmp.next = queue.peek();
//                }
//                if(tmp.left != null){
//                    queue.offer(tmp.left);
//                }
//                if(tmp.right != null){
//                    queue.offer(tmp.right);
//                }
//            }
//        }
//        return root;
//    }
//}




// LeetCode - 147. 对链表进行插入排序
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
//class Solution {
//    public ListNode insertionSortList(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode newHead = new ListNode();
//        newHead.next =  head;
//        ListNode lastSorted = head;
//        ListNode cur = head.next;
//        while(cur != null){
//            if(lastSorted.val <= cur.val){
//                lastSorted = lastSorted.next;
//            }else{
//                ListNode prev = newHead;
//                while(prev.next.val <= cur.val){
//                    prev = prev.next;
//                }
//                lastSorted.next = cur.next;
//                cur.next = prev.next;
//                prev.next = cur;
//            }
//            cur = lastSorted.next;
//        }
//        return newHead.next;
//    }
//}


//LeetCode - 116. 填充每个节点的下一个右侧节点指针
// 层序遍历 方法
//class Solution {
//    public Node connect(Node root) {
//        if(root == null){
//            return root;
//        }
//        Queue<Node> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            for(int i = 0;i < size;i++){
//                Node tmp = queue.poll();
//                if(i < size -1){
//                    tmp.next = queue.peek();
//                }
//                if(tmp.left != null){
//                    queue.offer(tmp.left);
//                }
//                if(tmp.right != null){
//                    queue.offer(tmp.right);
//                }
//            }
//        }
//        return root;
//    }
//}

// 使用已建立的 next 指针
//class Solution {
//    public Node connect(Node root) {
//        if(root == null){
//            return root;
//        }
//        Node leftRoot = root;
//        while(leftRoot.left!=null){
//            Node head = leftRoot;
//            while(head != null){
//                head.left.next = head.right;
//
//                // 说明 head 是有兄弟的
//                if(head.next!=null){
//                    head.right.next = head.next.left;
//                }
//
//                head = head.next;
//                // head 移动到兄弟结点
//                // 如果head没有兄弟结点，那么head == null;
//                // 刚好作为循环终止条件
//            }
//            // leftRoot 移动目前 “根结点”的左子树
//            leftRoot = leftRoot.left;
//
//        }
//        return root;
//    }
//}


// LeetCode - 114. 二叉树展开为链表
//class Solution {
//    public void flatten(TreeNode root) {
//        List<TreeNode> list = new ArrayList<>();
//        preorderTraversal(list,root);
//        int size = list.size();
//        for(int i = 1; i < size;i++){
//            TreeNode prev = list.get(i - 1),cur = list.get(i);
//            prev.left = null;
//            prev.right = cur;
//        }
//
//    }
//    private void preorderTraversal(List<TreeNode> list,TreeNode root){
//        if(root==null){
//            return;
//        }
//        list.add(root);
//        preorderTraversal(list,root.left);
//        preorderTraversal(list,root.right);
//    }
//}


// LeetCode - 109. 有序链表转换二叉搜索树
// 分治 -  平衡二叉搜索树
// class Solution {
//     public TreeNode sortedListToBST(ListNode head) {
//         return builderTree(head,null);
//     }
//     private TreeNode builderTree(ListNode left , ListNode right){
//         if(left == right){
//             return null;
//         }
//         ListNode mid = getMid(left,right);
//         TreeNode root  = new TreeNode(mid.val);
//         root.left = builderTree(left,mid);
//         root.right = builderTree(mid.next,right);
//         return root;
//     }
//     private ListNode getMid(ListNode left,ListNode right){
//         ListNode fast = left;
//         ListNode slow = left;
//         while(fast != right && fast.next != right){
//             fast =fast.next.next;
//             slow = slow.next;
//         }
//         return slow;
//     }
// }

// 分治 + 中序遍历 - 平衡二叉树
//class Solution {
//    private ListNode headTab;
//    public TreeNode sortedListToBST(ListNode head) {
//        headTab = head;
//        int len = getLen(head);
//        return builderTree(0,len - 1);
//    }
//    private int getLen(ListNode head){
//        int result = 0;
//        while(head != null){
//            result++;
//            head = head.next;
//        }
//        return result;
//    }
//    private TreeNode builderTree(int left,int right){
//        if(left > right){
//            return null;
//        }
//        int mid = (left + right + 1)/2;
//        TreeNode root = new TreeNode();
//        root.left = builderTree(left,mid -1);
//        root.val = headTab.val;
//        headTab = headTab.next;
//        root.right = builderTree(mid+1,right);
//        return root;
//    }
//}





// LeetCode - 225. 用队列实现栈
//class MyStack {
//    private Queue<Integer> queue1;
//    private Queue<Integer> queue2;
//    public MyStack() {
//        queue1 = new LinkedList<Integer>();
//        queue2 = new LinkedList<Integer>();
//    }
//
//    public void push(int x) {
//        queue1.offer(x);
//        while(!queue2.isEmpty()){
//            queue1.offer(queue2.poll());
//        }
//        Queue<Integer> tmp = queue1;
//        queue1 = queue2;
//        queue2 = tmp;
//    }
//
//    public int pop() {
//        return queue2.poll();
//    }
//
//    public int top() {
//       return queue2.peek();
//    }
//
//    public boolean empty() {
//        return queue2.size() == 0;
//    }
//}


// LeetCode - 496. 下一个更大元素 I
//class Solution {
//    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//        int m = nums1.length,n = nums2.length;
//        int[] result = new int[m];
//        for(int i = 0;i < m;i++){
//            int j = 0;
//            while(j < n && nums2[j] != nums1[i]){
//                j++;
//            }
//            int k = j + 1;
//            while(k < n && nums2[k] < nums1[i]){
//                k++;
//            }
//            result[i] = k < n ? nums2[k] : -1;
//        }
//        return result;
//    }
//}


// LeetCode - 1441. 用栈操作构建数组
//class Solution {
//    public List<String> buildArray(int[] target, int n) {
//        List<String> list = new ArrayList<>();
//        for(int i = 0,num = 1;i < target.length;i++){
//            list.add("Push");
//            if(num != target[i]){
//               list.add("Pop");
//               i--;
//            }
//            num++;
//        }
//        return list;
//    }
//}


// LeetCode -1171. 从链表中删去总和值为零的连续节点
// 方式一
//class Solution {
//    public ListNode removeZeroSumSublists(ListNode head) {
//        while(true){
//            ListNode newHead = sumIsZero(head);
//            if( newHead == head){
//                break;
//            }
//            head = newHead;
//        }
//        ListNode cur = head;
//        while(cur!=null){
//            ListNode curNext = sumIsZero(cur.next);
//            if(cur.next == curNext){
//                cur = curNext;
//            }else{
//                cur.next = curNext;
//            }
//        }
//        return head;
//    }
//    private ListNode sumIsZero( ListNode head){
//        if(head == null){
//            return head;
//        }
//        while(head != null && head.val == 0){
//            head = head.next;
//        }
//        ListNode cur = head;
//        int sum = 0;
//        while( cur!= null){
//            sum += cur.val;
//            if( sum == 0 ){
//                return cur.next;
//            }
//            cur = cur.next;
//        }
//        return head;
//    }
//}

// 方式二
//class Solution {
//    public ListNode removeZeroSumSublists(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode newHead = new ListNode(0,head);
//        ListNode prev = newHead;
//        while(prev != null) {
//            ListNode cur = prev.next;
//            int sum = 0;
//            while (cur != null) {
//                sum += cur.val;
//                if (sum == 0) {
//                    prev.next = cur.next;
//                    break;
//                } else {
//                    cur = cur.next;
//                }
//            }
//            if (cur == null) {
//                prev = prev.next;
//            }
//        }
//        return newHead.next;
//    }
//}





// LeetCode - 1154. 一年中的第几天
//class Solution {
//    public int dayOfYear(String date) {
//        int year = Integer.parseInt(date.substring(0,4));
//        int month = Integer.parseInt(date.substring(5,7));
//        int day = Integer.parseInt(date.substring(8));
//
//        int[] monthDay = {31,28,31,30,31,30,31,31,30,31,30,31};
//        if(year%400 == 0 || (year%4 == 0 && year%100 != 0)){
//            monthDay[1]++;
//        }
//        int dayCount = 0;
//        for(int i = 0; i < month-1;i++ ){
//            dayCount += monthDay[i];
//        }
//        dayCount += day;
//        return dayCount;
//    }
//}

//LeetCode - 1160. 拼写单词
//class Solution {
//    public int countCharacters(String[] words, String chars) {
//        int[] countChars = count(chars);
//        int len = 0;
//        for(String word : words){
//            int[] wordCount = count(word);
//            if(contain(countChars,wordCount)){
//                len += word.length();
//            }
//        }
//        return len;
//    }
//    private int[] count(String str){
//        int[] counter = new int[26];
//        for(int i = 0;i < str.length();i++){
//            counter[str.charAt(i) - 'a'] ++;
//        }
//        return counter;
//    }
//    private boolean contain(int[] str,int[] sub){
//        for(int i = 0;i < 26;i++){
//            if(str[i] < sub[i] ){
//                return false;
//            }
//        }
//        return true;
//    }
//}


// LeetCode - 面试题 01.02. 判定是否互为字符重排
//class Solution {
//    public boolean CheckPermutation(String s1, String s2) {
//        int lenS1 =  s1.length();
//        int lenS2 = s2.length();
//        if(lenS1 != lenS2){
//            return false;
//        }
//        char[] s1Array = new char[lenS2];
//        char[] s2Array = new char[lenS2];
//        for(int i = 0;i < lenS2;i++){
//            s1Array[i] = s1.charAt(i);
//            s2Array[i] = s2.charAt(i);
//        }
//        Arrays.sort(s1Array);
//        Arrays.sort(s2Array);
//            for(int i = 0;i < lenS2;i++){
//            if(s1Array[i] != s2Array[i]){
//                return false;
//            }
//        }
//        return true;
//    }
//}


//LeetCode - 278. 第一个错误的版本
//public class Solution extends VersionControl {
//    public int firstBadVersion(int n) {
//        int right = n,left = 0;
//        while(right > left){
//            int mid = left + (right -left)/2;
//            if(isBadVersion(mid)){
//                right = mid;
//            }else{
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//}

// LeetCode -35. 搜索插入位置
//class Solution {
//    public int searchInsert(int[] nums, int target) {
//        int n = nums.length;
//        int left = 0,right = n - 1,result = n;
//        while(left < right){
//            int mid = left + (right -left)>>>1;
//            if(target <= nums[mid]){
//                result = mid;
//                right = mid - 1;
//            }else{
//                left = mid + 1;
//            }
//        }
//        return result;
//    }
//}

// LeetCode -374. 猜数字大小

//public class Solution extends GuessGame {
//    public int guessNumber(int n) {
//        int left = 1,right = n;
//        while(left < right){
//            int mid = left + (right -left) / 2;
//            if(guess(mid) <= 0){
//                right = mid;
//            }else{
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//}

// LeetCode -258. 各位相加
//class Solution {
//    public int addDigits(int num) {
//        while(num > 9){
//            int next = 0;
//            while(num > 0){
//                next += num%10;
//                num /= 10;
//            }
//            num = next;
//        }
//        return num;
//    }
//}

//class Solution {
//    public int addDigits(int num) {
//        return (num - 1) % 9 + 1;
//    }
//}

// LeetCode - 263. 丑数
//class Solution {
//    public boolean isUgly(int n) {
//        if(n == 0){
//            return false;
//        }
//        int[] factors = {2,3,5};
//        for(int factor: factors){
//            while(n % factor == 0){
//                n /= factor ;
//            }
//        }
//        return n == 1;
//    }
//}

// LeetCode - 202. 快乐数
//class Solution {
//    private int getNext(int n){
//        int newNum = 0;
//        while(n > 0){
//            int d = n % 10;
//            n /= 10;
//            newNum += d * d;
//        }
//        return newNum;
//    }
//    public boolean isHappy(int n) {
//        int slowRun = n;
//        int fastRun = getNext(n);
//        while(fastRun != 1 && fastRun != slowRun){
//            slowRun = getNext(slowRun);
//            fastRun = getNext(getNext(fastRun));
//        }
//        return fastRun == 1;
//    }
//}

// LeetCode - 13. 罗马数字转整数
//class Solution {
//    Map<Character,Integer> symbolVal = new HashMap<Character,Integer>(){{
//        put('I',1);
//        put('V',5);
//        put('X',10);
//        put('L',50);
//        put('C',100);
//        put('D',500);
//        put('M',1000);
//    }};
//    public int romanToInt(String s) {
//        int result =0;
//        int n = s.length();
//        for(int i = 0;i < n; i++){
//            int value = symbolVal.get(s.charAt(i));
//            if(i < n - 1 && value < symbolVal.get(s.charAt(i+1))){
//                result -= value;
//            }else{
//                result += value;
//            }
//        }
//        return result;
//    }
//}

// LeetCode - 27. 移除元素
//class Solution {
//    public int removeElement(int[] nums, int val) {
//        int len = nums.length;
//        if(len == 0){
//            return 0;
//        }
//        int left = 0;
//        for(int right = 0; right < len;right++){
//            if(nums[right] != val){
//                nums[left] = nums[right];
//                left++;
//            }
//        }
//        return left;
//    }
//}

// LeetCode - 373. 查找和最小的 K 对数字
//class Solution {
//    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//    // 创建 一个大小为 k 的 大根堆
//        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k,new Comparator<List<Integer>>(){
//            @Override
//            public int compare(List<Integer> o1,List<Integer> o2){
//                return ((o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1)));
//            }
//        });
//        // 我们不需要将数组 num1 和 num2 遍历完
//        // 因为 这两个数组是升序，前k个最小数对，一定是 有 num1 和 num2 前k 个元素 组成的。
//        for(int i = 0;i < Math.min(nums1.length,k);i++){
//            for(int j = 0;j < Math.min(nums2.length,k);j++){
//                  // 先放入 k 个 数对
//                if(maxHeap.size()< k){
//                    List<Integer> tmpList = new ArrayList<>();
//                    tmpList.add(nums1[i]);
//                    tmpList.add(nums2[j]);
//                    maxHeap.offer(tmpList);
//                }else{// 从 k +1 个 数对，开始判断
//                    int top = maxHeap.peek().get(0) +maxHeap.peek().get(1);
//                    if(top >(nums1[i] + nums2[j])){
//                        // 弹出
//                        maxHeap.poll();
//                        List<Integer> tmpList = new ArrayList<>();
//                        tmpList.add(nums1[i]);
//                        tmpList.add(nums2[j]);
//
//                        // 入队
//                        maxHeap.offer(tmpList);
//                    }
//                }
//            }
//        }
//        // 为返回值做准备
//        List<List<Integer>> result = new ArrayList<>();
//        // 循环判断条件，需要加上 一个判断 堆是不是为空
//        // 根据示例三：两个数组元素 可能存在 不足以构成 k 个最小数对 的情况
//        for(int i = 0; i < k && !maxHeap.isEmpty();i++ ){
//            result.add(maxHeap.poll());
//        }
//        return result;
//    }
//}


//LeetCode - 145. 二叉树的后序遍历
// 非递归
//class Solution {
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        TreeNode prev = null;
//        while(cur != null || !stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                cur = cur.left;
//            }
//            TreeNode tmp = stack.peek();
//            if(tmp.right == null || prev == tmp.right){
//                stack.pop();
//                list.add(tmp.val);
//                prev = tmp;
//            }else{
//                cur = tmp.right;
//            }
//        }
//        return list;
//    }
//}

//  递归
// class Solution {
//     List<Integer> list;
//     public List<Integer> postorderTraversal(TreeNode root) {
//         list = new ArrayList<>();
//         postorder(root);
//         return list;
//     }
//     public void postorder(TreeNode root){
//         if(root == null){
//             return;
//         }
//         postorder(root.left);
//         postorder(root.right);
//         list.add(root.val);
//     }
// }


//LeetCode - 94. 二叉树的中序遍历
// 非递归
//class Solution {
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        while(cur != null || !stack.isEmpty() ){
//            while(cur!=null){
//                stack.push(cur);
//                cur = cur.left;
//            }
//            TreeNode tmp = stack.pop();
//            list.add(tmp.val);
//            cur = tmp.right;
//        }
//        return list;
//    }
//}

//   递归
// class Solution {
//     List<Integer> list;
//     public List<Integer> inorderTraversal(TreeNode root) {
//         list = new ArrayList<>();
//         inorder(root);
//         return list;
//     }
//     public void inorder(TreeNode root){
//         if(root == null){
//             return;
//         }
//         inorder(root.left);
//         list.add(root.val);
//         inorder(root.right);
//     }
// }


//LeetCode - 144 二叉树的前序遍历
// 非递归
//class Solution {
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList();
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        while(cur != null || !stack.isEmpty()){
//            while(cur!= null){
//                list.add(cur.val);
//                stack.push(cur);
//                cur = cur.left;
//            }
//            TreeNode tmp = stack.pop();
//            cur = tmp.right;
//        }
//        return list;
//    }
//}

// 递归
// class Solution {
//     public List<Integer> preorderTraversal(TreeNode root) {
//         List<Integer> list = new ArrayList<>();
//         if(root == null){
//             return list;
//         }
//         list.add(root.val);
//          List<Integer> treeLeft = preorderTraversal(root.left);
//          list.addAll(treeLeft);

//          List<Integer> treeRight = preorderTraversal(root.right);
//          list.addAll(treeRight);

//          return list;
//     }

// }



// LeetCode - 662. 二叉树最大宽度
// 利用完全二叉树性质： 左孩子编号 == 父结点 * 2 + 1 ; 右孩子编号 == 父结点 * 2 + 2
//class Solution {
//    public int widthOfBinaryTree(TreeNode root) {
//        if(root == null){
//            return  0;
//        }
//        LinkedList<TreeNode> queue  = new LinkedList<>();
//        queue.offer(root);
//        root.val = 0;
//        int maxWidth = 0;
//        while(! queue.isEmpty()){
//            int size = queue.size();
//            int width = queue.peekLast().val - queue.peekFirst().val + 1;
//            while(size>0){
//                TreeNode tmp = queue.poll();
//                if(tmp.left != null){
//                    queue.offer(tmp.left);
//                    tmp.left.val = tmp.val * 2 + 1;
//                }
//                if(tmp.right != null){
//                    queue.offer(tmp.right);
//                    tmp.right.val = tmp.val * 2 + 2;
//                }
//                size--;
//            }
//            maxWidth = Math.max(maxWidth,width);
//        }
//        return maxWidth;
//    }
//}



// LeetCode - 897. 递增顺序搜索树
//class Solution {
//    public TreeNode increasingBST(TreeNode root) {
//        if(root == null){
//            return null;
//        }
//        List<Integer> list = new ArrayList<>();
//        inorder(root,list);
//        TreeNode head = new TreeNode();
//        TreeNode cur = head;
//        for(int n: list){
//            TreeNode node = new TreeNode(n);
//            cur.right = node;
//            cur = node;
//        }
//        return head.right;
//    }
//    public void inorder(TreeNode root,List<Integer> list){
//        if(root == null){
//            return;
//        }
//        inorder(root.left,list);
//        list.add(root.val);
//        inorder(root.right,list);
//    }
//}


// LeetCode - 606. 根据二叉树创建字符串
// class Solution {
//    public String tree2str(TreeNode root) {
//        if(root == null){
//            return "()";
//        }
//        StringBuilder sb = new StringBuilder();
//        preOrderChange(root,sb);
//        return sb.toString();
//    }
//    public void preOrderChange( TreeNode root, StringBuilder sb ){
//        if(root == null){
//            return;
//        }
//        sb.append(root.val);
//        if(root.left != null){
//            sb.append("(");
//            preOrderChange(root.left,sb);
//            sb.append(")");
//        }else{
//            // root.left == null;
//            if(root.right == null){
//                return ;
//            }else{
//                sb.append("()");
//
//            }
//        }
//        if( root.right == null){
//            return;
//        }else{
//            sb.append("(");
//            preOrderChange(root.right,sb);
//            sb.append(")");
//        }
//    }
//
//}


// LeetCode - 105. 从前序与中序遍历序列构造二叉树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        if(preorder == null || inorder == null){
//            return null;
//        }
//        return creationTree(preorder,inorder,0,inorder.length-1);
//    }
//    public int preorderIndex;
//    public TreeNode creationTree(int[] preorder,int[] inorder,int begin,int end){
//        if(end < begin){
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[preorderIndex]);
//        int rootIndex = findIndexOf(inorder,begin,end,preorder[preorderIndex]);
//        if(rootIndex == -1){
//            return null;
//        }
//        preorderIndex++;
//        root.left = creationTree(preorder,inorder,begin,rootIndex-1);
//        root.right = creationTree(preorder,inorder,rootIndex+1,end);
//        return root;
//    }
//    private int findIndexOf(int[] inorder,int begin,int end,int key){
//        for(int i = begin;i <= end;i++){
//            if(inorder[i] == key){
//                return i;
//            }
//        }
//        return -1;
//    }
//}


//牛客题霸 - JZ36 二叉搜索树与双向链表
//public class Solution {
//    public TreeNode Convert(TreeNode pRootOfTree) {
//        if(pRootOfTree == null){
//            return null;
//        }
//        inorderTraversal(pRootOfTree);
//        TreeNode head = pRootOfTree;
//        while(head.left != null){
//            head = head.left;
//        }
//        return head;
//    }
//    public TreeNode prev ;
//    public void inorderTraversal(TreeNode root){
//        if(root == null){
//            return;
//        }
//        inorderTraversal(root.left);
//        // 打印
//        root.left = prev;
//        if(prev != null){
//            prev.right = root;
//        }
//        prev = root;
////         System.out.print(root.val + " ");
//        inorderTraversal(root.right);
//    }
//}

// LeetCode - 236. 二叉树的最近公共祖先
// 搜索二叉树思想
// class Solution {
//     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//         // 终止条件
//         if(root == null){
//             return root;
//         }
//         // 根结点为 p 和 q 中一个
//         if(root == q || root == p){
//             return root == q ? q : p;
//         }
//         // 左子树 寻找 公共祖先
//         TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
//         // 右子树 寻找 公共祖先
//         TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
//         if(leftNode != null && rightNode != null){
//             return root;
//         }
//         return  leftNode == null ? rightNode : leftNode;
//     }
// }

// 链表交点 思想 - 快慢指针
//class Solution {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null){
//            return root;
//        }
//        Stack<TreeNode> stackq = new Stack<>();
//        Stack<TreeNode> stackp = new Stack<>();
//        getPath(root,p,stackp);
//        getPath(root,q,stackq);
//        int sizep = stackp.size();
//        int sizeq = stackq.size();
//        int difference = sizep - sizeq;
//        if(difference < 0 ){
//            difference = sizeq - sizep;
//            while(difference>0){
//                stackq.pop();
//                difference--;
//            }
//            while(!stackq.isEmpty() && !stackp.isEmpty() ){
//                TreeNode nodeq = stackq.pop();
//                TreeNode nodep = stackp.pop();
//                if(nodeq == nodep){
//                    return nodep;
//                }
//            }
//        }else{
//            while(difference>0){
//                stackp.pop();
//                difference--;
//            }
//            while(!stackq.isEmpty() && !stackp.isEmpty() ){
//                TreeNode nodeq = stackq.pop();
//                TreeNode nodep = stackp.pop();
//                if(nodeq == nodep){
//                    return nodep;
//                }
//            }
//        }
//        return null;
//    }
//    public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
//        if(root == null || node == null){
//            return false;
//        }
//        stack.push(root);
//        if(root == node){
//            return true;
//        }
//        boolean flag =getPath(root.left,node,stack);
//        if(flag){
//            return true;
//        }
//
//        flag =getPath(root.right,node,stack);
//        if(flag){
//            return true;
//        }
//        stack.pop();
//        return false;
//    }
//}


//LeetCode - 102. 二叉树的层序遍历
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> result = new ArrayList<>();
//        if(root == null){
//            return result;
//        }
//        Queue<TreeNode> q = new LinkedList<>();
//        q.offer(root);
//        while(!q.isEmpty()){
//            int size = q.size();// 记录当前队列的元素个数
//            List<Integer> list = new ArrayList<>();// 存储当前层次的元素
//            while(size > 0){// 将当前层次的元素 出队
//                TreeNode tmp = q.poll();// 出队
//                list.add(tmp.val);//  存入 list 中
//                size--;// 表示 将当前层次的元素存入完成。
//                // 同时，将该层次节点 的 下一层次的节点（左右子树） 存入
//                if(tmp.left != null){
//                    q.offer(tmp.left);
//                }
//                if(tmp.right != null){
//                    q.offer(tmp.right);
//                }
//            }
//            result.add(list);// 将每层的 list 存入 result 中
//        }
//        // 返回 结果
//        return result;
//    }
//}



//LeetCode - 101. 对称二叉树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public boolean isSymmetric(TreeNode root) {
//        // 二叉树为 空树
//        if(root == null){
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//    public boolean isSymmetricChild(TreeNode L,TreeNode R){
//        // 树的根结点 左右子树为null
//        if(L == null && R == null){
//            return true;
//        }
//        // 二叉树的左右子树有一棵子树为空树
//        if( (L == null && R != null) || (L != null && R == null) ){
//            return false;
//        }
//        // 继续判断：两棵树中 对称节点的值【左对右，右对左】
//        if(L.val == R.val){
//            return isSymmetricChild(L.left,R.right) &&isSymmetricChild(L.right,R.left);
//        }
//        return false;
//    }
//}

// LeetCode - 110. 平衡二叉树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public boolean isBalanced(TreeNode root) {
//        if(root == null){
//            return true;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
//
//    }
//    public int getHeight(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
//    }
//}

// LeetCode - 572. 另一棵树的子树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q == null){// 两棵二叉树都为空树
//            return true;
//        }
//        // 两棵儿茶素中，有一颗树为空树
//        if( (p != null && q == null) || (p == null && q != null) ){
//            return false;
//        }
//        // 判断 两棵二叉树中，两个相对应的位置节点val值是否相同【宏观：判断根结点 是否相同】
//        if(p.val != q.val){
//            return false;
//        }
//        // 宏观：
//        // 走到这里 说明两棵二叉树的头节点相同。接着，就是遍历 两棵二叉树的 左右子树。
//        // 必须 两棵二叉树的左右子树都相等【true】。再结合根结点。【true】
//        // 这两棵二叉树才能算是相同的树
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
//    }
//
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root == null){
//            return subRoot!=null ? false:true;
//        }
//        // 判断 是否是同一棵树
//        if(isSameTree(root,subRoot)){
//            return true;
//        }
//        // 判断 subRoot是否 是 root的左子树 或者 是左子树的一部分
//        if(isSubtree(root.left,subRoot)){
//            return true;
//        }
//        // 判断 subRoot是否 是 root的右子树 或者 是右子树的一部分
//        if(isSubtree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//
//}

// LeetCode - 100. 相同的树
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q == null){
//            return true;
//        }
//        if( (p != null && q == null) || (p == null && q != null) ){
//            return false;
//        }
//        if(p.val != q.val){
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
//    }
//}



//LeetCode - 682. 棒球比赛
//class Solution {
//    public int calPoints(String[] ops) {
//        Stack<Integer> stack = new Stack<>();
//        for(String s:ops){
//            if(isOperator(s)){
//                switch(s){
//                    case "C":
//                        stack.pop();
//                        break;
//                    case "D":
//                        int num = stack.peek();
//                        stack.push(num*2);
//                        break;
//                    case "+":
//                        int num2 = stack.pop();
//                        int num1 = stack.peek();
//                        stack.push(num2);
//                        stack.push(num1 + num2);
//                        break;
//                }
//
//            }else{
//                stack.push(Integer.parseInt(s));
//            }
//        }
//        int  result = 0;
//        while(!stack.isEmpty()){
//            result += stack.pop();
//        }
//        return result;
//    }
//    public boolean isOperator(String str){
//        if(str.equals("C") ||str.equals("D") || str.equals("+")){
//            return true;
//        }
//        return false;
//    }
//}

//LeetCode - 155. 最小栈
//class MinStack {
//    private Stack<Integer> stack;
//    private Stack<Integer> stackMin;
//    public MinStack() {
//        stack = new Stack<>();
//        stackMin = new Stack<>();
//    }
//
//    public void push(int val) {
//        stack.push(val);
//        if(stackMin.isEmpty()){
//            stackMin.push(val);
//        }else{
//            if(val <= stackMin.peek()){
//                stackMin.push(val);
//            }
//        }
//
//    }
//
//    public void pop() {
//        if(!stack.isEmpty()){
//            int val = stack.pop();
//            if(val == stackMin.peek() && !stackMin.isEmpty()){
//                stackMin.pop();
//            }
//        }
//
//    }
//
//    public int top() {
//        return stack.peek();
//
//    }
//
//    public int getMin() {
//        return stackMin.peek();
//    }
//}
//
///**
// * Your MinStack object will be instantiated and called as such:
// * MinStack obj = new MinStack();
// * obj.push(val);
// * obj.pop();
// * int param_3 = obj.top();
// * int param_4 = obj.getMin();
// */

//LeetCode - 20. 有效的括号
//class Solution {
//    public boolean isValid(String s) {
//        Stack<Character> stack = new Stack<>();
//        for(int i = 0;i < s.length();i++){
//            char ch = s.charAt(i);
//            if(ch == '(' || ch == '[' || ch == '{'){
//                stack.push(ch);
//            }else{
//                if(stack.isEmpty()){
//                    return false;
//                }
//                char top = stack.peek();
//                if(top == '(' && ch == ')'){
//                    stack.pop();
//                }else if(top == '[' && ch == ']'){
//                    stack.pop();
//                }else if(top == '{' && ch == '}'){
//                    stack.pop();
//                }else{
//                    return false;
//                }
//            }
//        }
//        return stack.isEmpty();
//    }
//}


//LeetCode - 844. 比较含退格的字符串
//class Solution {
//    public boolean backspaceCompare(String s, String t) {
//        Stack<Character> Sstack = new Stack<>();
//        Stack<Character> Tstack = new Stack<>();
//        for(int i = 0;i < s.length();i++){
//            char chs = s.charAt(i);
//            if(chs == '#'){
//                if(!Sstack.isEmpty())
//                Sstack.pop();
//            }else{
//                Sstack.push(chs);
//            }
//
//        }
//        for(int i = 0; i < t.length();i++){
//            char cht = t.charAt(i);
//            if( cht == '#'){
//                if(!Tstack.isEmpty())
//                Tstack.pop();
//            }else{
//                Tstack.push(cht);
//            }
//        }
//        while(!Sstack.isEmpty() && !Tstack.isEmpty()){
//            if(Sstack.pop() != Tstack.pop()){
//                return false;
//            }
//        }
//        return Sstack.isEmpty() && Tstack.isEmpty();
//    }
//}

//题霸 - JZ31 栈的压入、弹出序列
//import java.util.*;
//
//public class Solution {
//    public boolean IsPopOrder(int [] pushA,int [] popA) {
//      Stack<Integer> stack = new Stack<>();
//        for(int i = 0, j = 0;i < pushA.length;i++){
//            stack.push(pushA[i]);
//            while(!stack.isEmpty() && j < popA.length && stack.peek() == popA[j]){
//                j++;
//                stack.pop();
//            }
//        }
//        return stack.isEmpty();
//
//    }
//}

// LeetCode - 150. 逆波兰表达式求值
//class Solution {
//    public int evalRPN(String[] tokens) {
//        Stack<Integer> stack = new Stack<>();
//        for(int i = 0; i <tokens.length;i++){
//            String str = tokens[i];//获取下标为 i 字符串元素
//            if(isOperator(str)){// 如果 str 是运算符 为 true，否则为false
//                int num2 = stack.pop();// 获取 栈顶 的 两个数字数据（出栈）
//                int num1 = stack.pop();
//                switch(str){// 判断 str 具体是 哪一个字符串，就执行对应的运算，并将其结果入栈
//                    case "+":
//                        stack.push(num1 + num2);
//                        break;
//                    case "-":
//                        stack.push(num1 - num2);
//                        break;
//                    case "*":
//                        stack.push(num1 * num2);
//                        break;
//                    case "/":
//                        stack.push(num1 / num2);
//                        break;
//                }
//            }else{// 将 数字字符转换成 整形数据 存入 栈中
//                stack.push(Integer.parseInt(str));
//            }
//        }
//        return stack.pop();// 返回最终存入栈中的结果
//    }
//    public boolean isOperator(String s){// 判断 str 是运算符 返回 true；否则，返回 false
//        if(s.equals("+") || s.equals("-")|| s.equals("*") || s.equals("/")){
//            return true;
//        }
//        return false;
//    }
//}

// LeetCode - 747. 至少是其他数字两倍的最大数
//class Solution {
//    public int dominantIndex(int[] nums) {
//        int max1 = -1;
//        int max2 = -1;
//        int index = -1;
//        for(int i = 0;i <nums.length;i++){
//            if(nums[i] > max1){
//                max2 = max1;
//                max1 = nums[i];
//                index = i;
//            }else if(nums[i] > max2){
//                max2 = nums[i];
//            }
//        }
//        return max1 >= max2 * 2 ? index : -1;
//    }
//}



// 剑指 Offer II 029. 排序的循环链表
///*
//// Definition for a Node.
//class Node {
//    public int val;
//    public Node next;
//
//    public Node() {}
//
//    public Node(int _val) {
//        val = _val;
//    }
//
//    public Node(int _val, Node _next) {
//        val = _val;
//        next = _next;
//    }
//};
//*/
//
//class Solution {
//    public Node insert(Node head, int insertVal) {
//        if(head == null){
//            head = new Node(insertVal);
//            head.next = head;
//            return head;
//        }
//        Node cur  = head;
//        Node tmp = null;
//        while(cur != tmp){
//            if(tmp == null){
//                tmp = head;
//            }
//            if((cur.val <= insertVal && insertVal <= cur.next.val) || (cur.val > cur.next.val && (insertVal <= cur.next.val || insertVal >= cur.val))){
//                Node node =  new Node(insertVal,cur.next);
//                cur.next = node;
//                return head;
//            }
//            cur = cur.next;
//        }
//        // 链表每个节点的val值都一样
//        Node node =  new Node(insertVal,cur.next);
//        cur.next = node;
//        return head;
//    }
//}

//LeetCode - 递增的三元子序列
//class Solution {
//    public boolean increasingTriplet(int[] nums) {
//        int n = nums.length;
//        if(n < 3){// 该数组 容量至少为 3
//            return false;
//        }
//        // i 为 三元子序列中最小值
//        int i = nums[0];
//        // j 为 三元子序列中 中间值
//        int j = Integer.MAX_VALUE;//防止与 i 冲突，初始化为整形最大值
//        // 循环数组，寻找 大于 j 的 num[k],三元子序列中的最大值，（期间：i 与 j 的值，始终在更新，确保 i 最小，j其次）
//        for(int k = 1;k < n; k++){
//            if(nums[k] > j){// 第一次，肯定是不满足。正好用来 更新 i 或者 j 的值，下一次就不移动了哟
//                return true;
//            }else if(nums[k] > i){// 比 i 值大，更新 j 值，
//                j = nums[k];
//            }else{// 比 i 小，更新 i 值。
//                i = nums[k];
//            }
//        }
//        return false;
//    }
//}



//剑指 Offer II 022. 链表中环的入口节点
//public class Solution {
//    public ListNode detectCycle(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast!=null && fast.next!=null){
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow){
//                ListNode cur = head;
//                while(cur!= slow){
//                    cur = cur.next;
//                    slow = slow.next;
//                }
//                return cur;
//            }
//        }
//        return null;
//    }
//}


//剑指 Offer II 021. 删除链表的倒数第 n 个结点
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
//class Solution {
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if(head == null){
//            return head;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while(n-- > 0 && fast!=null){
//            fast = fast.next;
//        }
//        ListNode prev = null;
//        while(fast!=null){
//            fast = fast.next;
//            prev = slow;
//            slow = slow.next;
//        }
//        if(prev != null){
//            prev.next = slow.next;
//        }else if(head == slow){
//            return head.next;
//        }
//        return head;
//    }
//}

// LeetCode - 按键持续时间最长的键
//class Solution {
//    public char slowestKey(int[] releaseTimes, String keysPressed) {
//        int n = releaseTimes.length;
//        char result = keysPressed.charAt(0);
//        int timeMax = releaseTimes[0];
//        for(int i = 1;i < n;i++){
//            char ch = keysPressed.charAt(i);
//            int time = releaseTimes[i] - releaseTimes[i-1];
//            if(time > timeMax || (time == timeMax && ch > result)){
//                result = ch;
//                timeMax = time;
//            }
//        }
//        return result;
//    }
//}



// LeetCode - 89 - 格雷编码 - 二进制转格雷码
//class Solution {
//    public List<Integer> grayCode(int n) {
//        List<Integer> list = new ArrayList<>();
//        for(int i = 0;i < (1 << n);i++){
//            list.add((i >> 1) ^ i);
//        }
//        return list;
//    }
//}



//LeetCode - 1614 - 括号的最大嵌套深度
//class Solution {
//    public int maxDepth(String s) {
//        int count = 0;
//        int result = 0;
//        for(int i = 0;i < s.length();i++){
//            if(s.charAt(i)== '('){
//                count++;
//                result = Math.max(result,count);
//            }else if(s.charAt(i) == ')'){
//                count--;
//            }
//        }
//        return result;
//    }
//}

//LeetCode - 面试题 02.01. 移除重复节点
//HashSet方法
//class Solution {
//    public ListNode removeDuplicateNodes(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        Set<Integer> occurred = new HashSet<>();
//        occurred.add(head.val);
//        ListNode pos = head;
//        while(pos.next!=null){
//            ListNode cur = pos.next;
//            if(occurred.add(cur.val)){
//                pos =  pos.next;
//            }else{
//                pos.next =pos.next.next;
//            }
//        }
//        return head;
//    }
//}

// 双循环
//class Solution {
//    public ListNode removeDuplicateNodes(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode cur1 = head;
//        while(cur1 != null){
//            ListNode cur2 = cur1;
//            while(cur2.next!=null){
//                if(cur2.next.val == cur1.val){
//                    cur2.next =cur2.next.next;
//                }else{
//                    cur2 =cur2.next;
//                }
//            }
//            cur1 =cur1.next;
//        }
//        return head;
//    }
//}



// LeetCode - 71 = 简化路径
//class Solution {
//    public String simplifyPath(String path) {
//        String[] str = path.split("/");
//        Deque<String> stack  = new ArrayDeque<>();
//        for(String name: str){
//            if("..".equals(name)){//如果遇到 ".."
//                if(!stack.isEmpty()){// 前提是 栈不为空。要不然，下面的操作会抛出异常。【另外：栈为空，你能删除什么？】
//                    stack.pollLast();// 删除 栈底 数据
//                }
//            }else if(name.length() > 0 && !".".equals(name)){//  长度为零的字符串 和 "." 不作为存储数据
//                stack.offerLast(name);// 将符合条件的数据，放入栈底
//            }
//        }
//        StringBuilder sb = new StringBuilder();
//        if(stack.isEmpty()){
//            sb.append("/");
//        }else{
//            while(!stack.isEmpty()){
//                sb.append("/");
//                sb.append(stack.pollFirst());
//            }
//        }
//        return sb.toString();
//    }
//}


// LeetCode - 2095. 删除链表的中间节点
//class Solution {
//    public ListNode deleteMiddle(ListNode head) {
//        if(head == null){
//            return head;
//        }
//        if(head.next==null){
//            return head.next;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode prev = null;
//        while(fast != null && fast.next != null){
//            fast = fast.next.next;
//            prev = slow;
//            slow = slow.next;
//        }
//        prev.next =slow.next;
//        return head;
//    }
//}



// LeetCode - 2074 -反转偶数长度组的节点
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
//class Solution {
//    public ListNode reverseEvenLengthGroups(ListNode head) {
//        ListNode prevHead = new ListNode();
//        prevHead.next = head;
//        ListNode tail = head;
//        int flag = 0;
//        for(int i = 1; flag == 0;i++){
//            ListNode reverseHead = prevHead;
//            ListNode reverseTail = null;
//            int count = 0;
//            while(tail!=null && count < i){
//                reverseTail =  tail;
//                prevHead = prevHead.next;
//                tail =tail.next;
//                count++;
//                if(tail == null){// 链表节点已分配完
//                    flag = 1;
//                }
//            }
//            if(count % 2 == 0){
//                prevHead = reverse(reverseHead,reverseTail);
//            }
//        }
//        return head;// 因为第一组是只有一节点，不用反转，也就是说 head 没有改变，直接返回就行了。
//    }
//    public ListNode reverse(ListNode prevHead,ListNode tail){
//        ListNode head = prevHead.next;
//        ListNode cur = head;
//        ListNode prev = tail.next;
//        while(prev != tail){
//            ListNode curNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        prevHead.next = tail;
//        return head;
//    }
//}



// LeetCode - 1669. 合并两个链表
//class Solution {
//    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
//        ListNode begin = list1;// 记录 list1 下标为 a 的前驱节点
//        ListNode end =  list1;// 记录 list1 下标 b 为 b 的 后驱节点
//        for(int i = 0;i < a-1;i++){// 找到下标为 a -1 的节点，也就是 下标为 a 的前驱节点
//            begin = begin.next;
//        }
//        for(int i = 0;i < b+1;i++){// 找到 下标为 b 的 后驱节点
//            end = end.next;
//        }
//        ListNode cur = list2;
//        while(cur.next != null){// 找到list2的尾节点
//            cur = cur.next;
//        }
//        begin.next = list2;
//        cur.next = end;
//        return list1;
//    }
//}


//LeetCode - 1171. 从链表中删去总和值为零的连续节点
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
//class Solution {
//    public ListNode removeZeroSumSublists(ListNode head) {
//        while(true){
//            ListNode newHead = sumIsZero(head);
//            if(newHead == head){
//                break;
//            }
//            head = newHead;
//        }
//        ListNode cur = head;
//        while(cur!=null){
//            ListNode next = sumIsZero(cur.next);
//            if(cur.next == next){
//                cur = cur.next;
//            }else{
//                cur.next = next;
//            }
//        }
//        return head;
//    }
//    public ListNode sumIsZero(ListNode head){
//        if(head == null){
//            return head;
//        }
//        if(head.val == 0){
//            return head.next;
//        }
//        ListNode cur = head;
//        int sum = 0;
//        while(cur!=null){
//            sum += cur.val;
//            if(sum == 0){
//                return cur.next;
//            }
//            cur = cur.next;
//        }
//        return head;
//    }
//}


//LeetCode - 1185. 一周中的第几天
// 解法一：
//class Solution {
//    public String dayOfTheWeek(int day, int month, int year) {
//        String[] week = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
//        int[] monthDay = {31,28,31,30,31,30,31,31,30,31,30};
//        int days = 4;
//        for(int i  = 1971; i < year; i++){
//            boolean leap = i%400 == 0 || (i % 4 == 0 && i % 100 !=0);
//            days +=  leap ? 366 :365;
//        }
//        for(int i = 0;i < month-1;i++){
//            days += monthDay[i];
//            if(i == 2 && (year % 400 == 0 || year % 4 == 0 && year % 100 !=0)){
//                days += 1;
//            }
//        }
//        days += day;
//        return week[days % 7];
//    }
//}

//解法二
//class Solution {
//    public String dayOfTheWeek(int day, int month, int year) {
//        String[] week = {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
//        int[] monthDay = {31,28,31,30,31,30,31,31,30,31,30};
//        int days = 365 * (year - 1971) + (year - 1969)/4;
//        for(int i = 0;i < month-1;i++){
//            days += monthDay[i];
//        }
//        if((year%400 == 0 || (year%4==0 && year%100!=0)) && month>2){
//            days += 1;
//        }
//        days += day;
//        return week[(days+3) % 7];
//    }
//}

// LeetCode - 390 -消除游戏
//class Solution {
//    public int lastRemaining(int n) {
//        int firstNum = 1;// 删除后，数组的第一个元素
//        int k =0;// 删除次数，k == 0表示这组数据没有被删除任何元素
//        int tolerance = 1;// 记录公差，无论正向还是反向删除，每删除一次，公差变为自身的两倍
//        int curNum = n;//记录数字个数
//        while(curNum > 1){
//            if(k % 2 == 0){//以偶数为 正向删除标准，奇数为反向删除标志.而且第一次删除是正向删除。
//                firstNum += tolerance;
//            }else{// 奇数 为反向删除，需要判断奇偶性
//                firstNum = (curNum % 2 ==0) ? firstNum : firstNum + tolerance;
//            }
//            k++;
//            tolerance = tolerance << 1;
//            curNum = curNum >> 1;
//        }
//        return firstNum;
//    }
//}


// LeetCode - 430 扁平化多级双向链表
///*
//// Definition for a Node.
//class Node {
//    public int val;
//    public Node prev;
//    public Node next;
//    public Node child;
//};
//*/
//
//class Solution {
//    public Node flatten(Node head) {
//        pancake(head);
//        return head;
//    }
//    public Node pancake(Node node){
//        Node cur = node;
//        Node last = null;
//        while(cur!=null){
//            Node next = cur.next;
//            if(cur.child != null){
//                Node childLast = pancake(cur.child);
//
//                next = cur.next;
//
//                cur.next = cur.child;
//                cur.child.prev = cur;
//
//                if(next !=  null){
//                    childLast.next = next;
//                    next.prev = childLast;
//                }
//                cur.child = null;
//                last = childLast;
//            }else{
//                last = cur;
//            }
//            cur = next;
//        }
//        return last;
//    }
//}
//}
//}
//}
//}


//LeetCode - 2022 - 将一维数组变成二维数组
//class Solution {
//    public int[][] construct2DArray(int[] original, int m, int n) {
//        if(original.length != m * n){
//            return new int[0][];
//        }

//        int[][] array = new int[m][n];

               // 方法一 System.arraycopy()
//        // for(int i = 0;i < original.length;i+=n){
//        //     System.arraycopy(original,i,array[i/n],0,n);
//        // }

          // 双重循环拷贝
//        int o = 0;// 用来记录 拷贝到 original数组中第几个元素的下标
//        for(int i = 0;i < m; i++){
//            for(int j = 0; j < n; j++){
//                array[i][j] = original[o];
//                o++;
//            }
//        }
//        return array;
//    }
//}




//LeetCode - 846. 一手顺子
//class Solution {
//    public boolean isNStraightHand(int[] hand, int groupSize) {
//        Arrays.sort(hand);
//        int n = hand.length;
//        int count = 0;
//        for(int i = 0; i < n;i++){
//            if(hand[i]== -1){//顺子中出现过的牌，直接跳过
//                continue;
//            }
//            count = 0;
//            for(int j = i+1; j < n && count != groupSize-1;j++){
//                if(hand[j] - hand[i] == count + 1){
//                    // 判断是否 满足顺子条件：第二张牌 比 第一张牌大一点，第三张比第一张大两点。
//                    // 以此类推： 第 groupSize张牌，比第一张牌大 groupSize -  1 点
//                    // 所以 count 就是用来记录 每张牌（除了第一张） 与 第一张牌的大小关系。
//                    // 顺便可以作为 循环限制条件（数组hand，可以发为 groupSize组 和 每组有 groupSize 张 ）
//                    // 至于为什么要减一，那是因为 第一张牌是用来比较的基准，而且已经 i “拿走了”。
//                    // 所以我们 只需要判断 hand[i] 后面 groupSize-1 张牌。
//
//                    hand[j] = -1;// 表示这张牌出现过
//                    count++;
//                }
//            }
//            if(count != groupSize - 1){// 如果循环结束时，count 的最终结果并不满足顺子条件，返回false。
//                return false;
//            }
//        }
//        return true;
//        // 整个循环结束时，并且走到这一步，说明 hand 数组，确实可以将牌分为  groupSize组，每组有  groupSize张牌。
//        // 且为顺子关系。
//    }
//}


//LeetCode - 445 - 两数相加||
//class Solution {
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        Deque<Integer> stack1 = new LinkedList<>();
//        Deque<Integer> stack2 = new LinkedList<>();
//
//        while(l1 != null){
//            stack1.push(l1.val);
//            l1 = l1.next;
//        }
//        while(l2 != null){
//            stack2.push(l2.val);
//            l2 = l2.next;
//        }
//        int carry = 0;// 进位数
//        ListNode head = null;// 头节点
//        while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){
//            int val1 = stack1.isEmpty() ? 0 : stack1.pop();
//            int val2 = stack2.isEmpty() ? 0 : stack2.pop();
//            int sum = val1 + val2 + carry;
//            carry = sum/10;
//            ListNode node = new ListNode(sum%10);
//            node.next = head;
//            head = node;
//        }
//        return head;
//    }
//}


//LeetCode - 328 - 奇偶链表
// 解法一
//class Solution {
//    public ListNode oddEvenList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode evenLinked = new ListNode();// 偶数链表头节点
//        ListNode evenCur = evenLinked;// 偶数链表头节点的替身
//        ListNode oddLinked = new ListNode();// 奇数链表头节点
//        ListNode oddCur = oddLinked;// 奇数链表头节点替身
//        int n  = 1;// 用来表示 现在 head 指向的是第几个节点，方便我们来判断个数的奇偶性
//        while(head!=null){
//            if(n % 2 != 1){//判断 第 n 个节点， n 是否偶数，是就接入偶数链表
//                evenCur.next = head;
//                evenCur = evenCur.next;
//            }else{//  第 n 个节点， n 既然不是偶数，那就是奇数了，就接入奇数链表
//                oddCur.next = head;
//                oddCur = oddCur.next;
//            }
//            head = head.next;// head 继续遍历原链表
//            n++;// 此时 head 指向了 第 n +1 个节点
//        }
////因为偶数位置的节点放在右边的，所以需要注意偶数链表最后一个节点的next，需要置为null。防止造成环！
//        evenCur.next = null;
//        oddCur.next = evenLinked.next;// 将奇数链表 和 偶数链表结合，其结果就是我们想要的
//
//        return oddLinked.next;// 在合并后，奇数链表的节点是前面的，所以我们返回 奇数链表的头节点的next。
//        // 因为我们奇数链表是一个带头的链表，所有头节点的值是不重要的！
//    }
//}

// 解法二
//class Solution {
//    public ListNode oddEvenList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode odd = head;
//        ListNode even = head.next;
//        ListNode evenCur = even;
//        while(evenCur != null && evenCur.next != null){
//            odd.next = evenCur.next;
//            odd = odd.next;
//            evenCur.next = odd.next;
//            evenCur = evenCur.next;
//        }
//        odd.next = even;
//        return head;
//    }
//}



// LeetCode - 825 - 适龄的朋友
//1.双指针 + 排序
//class Solution {
//    public int numFriendRequests(int[] ages) {
//        Arrays.sort(ages);
//        int n  = ages.length;
//        int left = 0,right = 0,result=0;
//        for(int age : ages){
//            if( age < 15){
//                // 不考虑 15岁以下的，这是题目隐藏条件，你不信邪，就加上等于，或者删除这个代码块
//                continue;// 后面程序不执行，继续foreach 循环 读取数据。
//            }
//            while(ages[left] <= 0.5*age +7){// 太小的，不合适，left++，范围缩小
//                left++;
//            }
//            while(right+1 < n && ages[right+1] <= age){// 年龄合适
//                right++;
//            }
//            result += right -left;// 累计每个人 发出好友请求
//        }
//        return result;// 返回 所有人 发送好友请求的信息条数。
//    }
//}

//  计数排序 + 前缀和
//class Solution {
//    public int numFriendRequests(int[] ages) {
//        int[] cnt = new int[121];
//        for (int age : ages) {
//            ++cnt[age];
//        }
//        int[] pre = new int[121];
//        for (int i = 1; i <= 120; ++i) {
//            pre[i] = pre[i - 1] + cnt[i];
//        }
//        int ans = 0;
//        for (int i = 15; i <= 120; ++i) {
//            if (cnt[i] > 0) {
//                int bound = (int) (i * 0.5 + 7);
//                ans += cnt[i] * (pre[i] - pre[bound] - 1);
//            }
//        }
//        return ans;
//    }
//}




// LeetCode - 143. 重排链表
//解法一(快慢指针 + 反转 + 合并)
//class Solution {
//    // 无返回值
//    public void reorderList(ListNode head) {
//        if( head == null){
//            return;
//        }
//        // 得到中间节点
//        ListNode mid = myMidNode(head);
//
//        // 分割链表
//        ListNode l1 = head;
//        ListNode l2 = mid.next;
//        mid.next = null;
//
//        // 下部分链表 反转
//        l2 = myReverse(l2);
//
//        // 上下两部分链表合并
//        mergeLinked(l1,l2);
//    }
//    public static void mergeLinked(ListNode l1,ListNode l2){
//        ListNode l1_tmp = null;// 用来记录 l1 的 next
//        ListNode l2_tmp = null;// 用来记录 l2 的 next
//
//        while(l1!=null && l2 != null){
//            l1_tmp = l1.next;
//            l2_tmp = l2.next;
//
//            l1.next = l2;
//            l1 = l1_tmp;
//
//            l2.next = l1;
//            l2 = l2_tmp;
//        }
//    }
//
//    public static ListNode myReverse(ListNode head){
//        ListNode prev = null;
//        ListNode cur = head;
//        while(cur!=null){
//            ListNode curNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        return prev;
//    }
//
//    public static ListNode myMidNode(ListNode head){
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast!=null && fast.next!=null){
//            fast = fast.next.next;
//            slow =slow.next;
//        }
//        return slow;
//    }
//}

// 解法二 线性表
//class Solution {
//    public void reorderList(ListNode head) {
//        if( head == null){
//            return;
//        }
//        List<ListNode> list = new ArrayList<>();
//
//        ListNode node = head;
//        while(node!=null){
//            list.add(node);
//            node = node.next;
//        }
//
//        int n = list.size();
//        int j  = n -1;
//        int i = 0;
//        while(i < j){
//            list.get(i).next = list.get(j);
//            i++;
//            if(i == j){
//                break;
//            }
//
//            list.get(j).next = list.get(i);
//            j--;
//        }
//        list.get(i).next = null;
//    }
//}




// LeetCode - 138 - 赋值带随机指针的链表
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

//class Solution {
//    public Node copyRandomList(Node head) {
//        if(head == null){
//            return head;
//        }
//        for(Node node = head; node!=null;node =node.next.next){
//            Node newNode = new Node(node.val);
//            newNode.next = node.next;
//            node.next = newNode;
//        }
//
//        for(Node node = head; node!=null;node = node.next.next){
//            Node newNode = node.next;
//            newNode.random = (node.random != null) ? node.random.next:null;
//        }
//
//        Node newHead = head.next;
//        for(Node node = head;node!=null;node = node.next){
//            Node newNode = node.next;
//            node.next = node.next.next;
//            newNode.next = (newNode.next != null) ? newNode.next.next : null;
//        }
//        return newHead;
//    }
//}


//LeetCode - 1705 - 吃苹果的最大数目
//class Solution {
//    public int eatenApples(int[] apples, int[] days) {
//        int result = 0; // 最终结果 - 最多吃几个苹果
//        int n = apples.length;// 获取在老家待多少天。
//        int i = 0;// 记录天数，用来对比保质期
//        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);// 每次取出的数据,都是保质期最短的那一组
//        while(i<n){
//            while(!pq.isEmpty() && pq.peek()[0] <= i){//检查 今天是否有某一天的苹果腐烂了（到保质期了）。
//                // pq.peek() 是返回队列中的头元素。因为我们是优先队列，所以 最快坏掉的苹果，就放在头位置
//                pq.poll();// 到期了，就扔掉。由此我们知道 poll 就删除出队列元素的方法
//            }
//            int rottenDay = i + days[i];// 记录当天产出苹果的保质期
//            int count = apples[i];// 记录 当天产出的苹果数量
//            if(count > 0){// 只有产出苹果，才有被记录信息的价值
//                pq.offer(new int[]{rottenDay,count});// 你现在可以看看 while(i<n)后面 while循环的条条件为什么是让 队列的头元素，来比较，
//            }
//            if(!pq.isEmpty()){// 这个if语句是为了防止 某天没有产出苹果，刚好又没有存货。
//                int[] arr = pq.peek();//获取 队列头元素,或者说：获取某天产出苹果（保质期最短的）信息
//                arr[1]--;// 每天吃的那一个苹果。
//                if(arr[1]==0){// 把某天快坏的苹果吃完了
//                    pq.poll();// 那就没必要记着该天的苹果信息
//                }
//                result++;// 我们此时吃到了一个苹果
//            }
//            i++;// 过去了一天
//        }
//
//        // 回去的那天，带回来的苹果
//        while(!pq.isEmpty()){//防止这几天产出的苹果，刚好够吃。所以队列中也就没有数据（没有苹果可以带走）
//            while(!pq.isEmpty() && pq.peek()[0]<=i){
//                // 这个跟上面的那个 while循环是一样的，检查有没有那天的苹果到了日期。
//                pq.poll();//到期， 丢掉。
//            }
//            if(pq.isEmpty()){// 昨天带回来的苹果，今天就全烂了,丢完了。队列中自然就是空的，没有数据
//                break;// 那就没必要进行下一步，直接终止循环，返回 最终结果 result。
//            }
//            //如果程序走到这里，说明不满足循环 和 if 条件。
//            // 意味着：有口福了，今天还有苹果可以吃
//            int[] arr = pq.poll();// 获取某天最快坏掉的苹果信息（保质期，和个数）
//
//
//            int eatDay = Math.min(arr[0]- i,arr[1] );//
//            // 首先，我们肯定只会吃没腐烂的苹果,其次我们每天只吃一个。
//            // 保质期减去今天，不就是苹果还有几天过期？ 又可以说 一天吃一个苹果可以吃几天。
//            // 但是可能存在 吃不完苹果，导致腐烂的情况，或者说 在苹果坏掉之前，刚好吃完。
//            // 所以我们要选取最小值，来保证每天迟到苹果不是坏的。
//
//            // 我们吃的 苹果数量 和 天数 同时 加上 eatDay。 （一天一个苹果）
//            result += eatDay;
//            i += eatDay;
//        }
//        return result;// 返回我们最终吃进肚子里的苹果总数
//    }
//}

// LeetCode 82. 删除排序链表中的重复元素 II
//class Solution {
//    public ListNode deleteDuplicates(ListNode head) {
//        if(head == null ){
//            return head;
//        }
//        ListNode newHead = new ListNode();
//        newHead.next =  head;
//        ListNode cur = newHead;
//        while(cur.next!=null && cur.next.next!=null){
//            if(cur.next.val == cur.next.next.val){
//                int x = cur.next.val;
//                while(cur.next!=null && cur.next.val == x){
//                    cur.next = cur.next.next;
//                }
//            }else{
//                cur = cur.next;
//            }
//        }
//        return newHead.next;
//    }
//}

// LeetCode - 25. K 个一组翻转链表
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode reverseKGroup(ListNode head, int k) {
//        ListNode newHead = new ListNode();
//        newHead.next = head;
//        ListNode prev = newHead;
//
//        while(head!=null){
//            ListNode tail = prev;
//            for(int i = 0;i < k;i++){
//                tail = tail.next;
//                if(tail == null){
//                    return newHead.next;
//                }
//            }
//
//            ListNode tailNextLogo = tail.next;
//            ListNode[] reverse = myReverse(head,tail);
//            head = reverse[0];
//            tail = reverse[1];
//
//            prev.next = head;
//            tail.next =tailNextLogo;
//
//            prev = tail;
//            head = tail.next;
//        }
//        return newHead.next;
//    }
//    public static ListNode[] myReverse(ListNode head,ListNode tail){
//        ListNode prev = tail.next;
//        ListNode p = head;
//        while(prev != tail){
//            ListNode pNext = p.next;
//            p.next = prev;
//            prev = p;
//            p = pNext;
//        }
//        return new ListNode[]{tail,head};
//    }
//
//}

//LeetCode - 24 - 两两交换链表中等的节点
//class Solution {
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next== null){
//            return  head;
//        }
//        ListNode newHead = head.next;
//        head.next = swapPairs(newHead.next);
//        newHead.next = head;
//        return newHead;
//    }
//}



// LeetCode - 997 -找到小镇的法官
//class Solution {
//    public int findJudge(int n, int[][] trust) {
//        int[] poll = new int[n+1];// 该数组每个元素都为0，刚好符合未开始投票的情况
//        for(int i = 0;i < trust.length;i++){
//            poll[trust[i][0]]--;//  a 投票
//            poll[trust[i][1]]++;//  b 获得 a 的投票
//        }
//        int judge = -1;
//        for(int i = 1 ;i<poll.length;i++){
//            if(poll[i]==n-1){
//                judge = i;
//                break;
//            }
//        }
//        return judge;
//    }
//}



// 实现 KMP 算法
//public class Manuscript {
//    /*
//    * @param str 主串
//    * @param sub 子串
//    * @param pos 从主串的pos位置开始匹配
//    * @return  找到 子串 在主串当中的 下标
//    * */
//    public static int KMP(String str,String sub,int pos){
//        if (str == null || sub == null){
////不管是主串，还是子串为null，你都查找不了 子串 在 主串中的位置
//            return  -1;// 此时返回返回-1 表示找不到，或者说无法查找
//        }
//
//        int lenStr = str.length();//获取主串的长度
//        int lenSub = sub.length();//获取子串的长度
//
//        if(lenStr == 0 || lenStr==0){
// // 这种情况也不用去想，空字符串里面一个元素都没有，肯定也比不了！
//            return  -1;
//        }
//        if (pos < 0 || pos > str.length()){
//            // 你规定查找位置不合法，如果不写，很可能会导致越界异常，导致程序终止
//            return -1;
//        }
//
//        int i = pos;// 从指定的 pos 位置，开始遍历 主串
//        int j = 0;// 遍历 子串
//
//        int[] next = new int[lenSub];// 创建一个 next数组，长度 与 子串一致
//        getNext(sub,next);// 得到next 数组
//
//        while(i < lenStr && j < lenSub){
//            if(j==-1 || str.charAt(i)==sub.charAt(j)){// 这就是主串 和 子串匹配成功的情况
//                //  j == -1. 是为了处理i 和 j 指向字符不匹配的情况
//                //  j 回退的时候，在next数组中，一直没有 p[j] == p[k]的情况出现
//                // j 回退到 -1 的情况，也就是没有相同的真子串情况 p[0]~ p[k-1] != p[j-k] ~ p[j-1]
//                // 另外 这个条件需要放在前面，放在后 charAt一读取，就会发生越界异常
//                i++;
//                j++;
//            }else{
//                j = next[j];
//            }
//        }
//        if (j >=lenSub){
//            return i-j;
//        }
//        // 主串 不包含 子串的情况，也就是 i 与 j 不匹配，j 一直在子串的下标0位置待命
//        // 即 j < lenSub
//        return -1;
//
//    }
//    public static void getNext(String sub,int[] next){
//        next[0] = -1;
//        next[1] = 0;
//        int j = 2;// 提前走了一步
//        int k = 0;
//        while(j< sub.length()){// 遍历 子串
//            // p[j] == p[k]
//            if(k== -1 || sub.charAt(j-1) == sub.charAt(k)){
//                next[j] = k + 1;
//                j++;
//                k++;
//            }else {// p[j-1] != p[k], j需要回退
//                k = next[k];
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        System.out.println(KMP("abababcabcdef","abcd",0));//7
//        System.out.println(KMP("abababcabcabcdef","abcdf",0));// -1
//        System.out.println(KMP("abababcabcabcdef","ab",0));//0
//    }
//}



// LeetCode - 807. 保持城市天际线
//给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
//城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。
//我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。
//在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。
//class Solution {
//    public int maxIncreaseKeepingSkyline(int[][] grid) {
//        int n = grid.length;
//        int[] rowMax = new int[n];
//        int[] colMax = new int[n];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                rowMax[i] = Math.max(rowMax[i],grid[i][j]);
//                colMax[j] = Math.max(colMax[j],grid[i][j]);
//            }
//        }
//        int count = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                count += Math.min(colMax[j],rowMax[i]) - grid[i][j];
//            }
//        }
//        return count;
//    }
//}
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        sc.nextLine();
//        int[][] grid = new int[n][n];
//        int m = 0;
//        while(m<n){
//            System.out.print("请一次输入"+ n +" 个整数，且用逗号隔开:");
//            String tmp = sc.nextLine();
//            String[] str = tmp.split(",");
//
//            int[] array = new int[str.length];
//            for (int i = 0; i < array.length; i++) {
//                array[i] = Integer.parseInt(str[i]);
//            }
//            grid[m] = array;
//            m++;
//        }
//        Solution solution = new Solution();
//        System.out.println(solution.maxIncreaseKeepingSkyline(grid));
//    }
//}


// LeetCode - 506 - 相对名次
//名次第 1 的运动员获金牌 "Gold Medal" 。
//名次第 2 的运动员获银牌 "Silver Medal" 。
//名次第 3 的运动员获铜牌 "Bronze Medal" 。
//从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。
//使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况
//class Solution {
//    public String[] findRelativeRanks(int[] score) {
//        int n = score.length;
//        String[] str1 = {"Gold Medal","Silver Medal","Bronze Medal"};
//        int[][] arr = new int[n][2];
//        for (int i = 0; i < n; i++) {
//            arr[i][0] = score[i];
//            arr[i][1] = i;
//        }
//        Arrays.sort(arr,(a,b)->b[0] - a[0]);
//        String[] str2 =  new String[n];
//        for (int i = 0; i < n; i++) {
//            if(i<3){
//                str2[arr[i][1]] = str1[i];
//            }else{
//                str2[arr[i][1]] = Integer.toString(i+1);
//            }
//        }
//        return str2;
//    }
//}
//public class Manuscript{
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int[] score =  new int[sc.nextInt()];
//        int n  = score.length;
//        int i = 0;
//        while(n--!=0 && sc.hasNextInt()){
//            score[i++] = sc.nextInt();
//        }
//        Solution solution = new Solution();
//        String[] str = solution.findRelativeRanks(score);
//        System.out.println(Arrays.toString(str));
//        sc.close();
//    }
//}



// LeetCode - 748.补全最短词
//class Solution {
//    public String shortestCompletingWord(String licensePlate, String[] words) {
//        int[] array1 = new int[26];
//        for (int i = 0; i < licensePlate.length(); i++) {
//            char ch = licensePlate.charAt(i);
//            if (Character.isLetter(ch)){
//                array1[Character.toLowerCase(ch) - 'a']++;
//            }
//        }
//        int index = -1;
//        for (int i = 0; i < words.length; i++) {
//            int[] array2 = new int[26];
//            for (int j = 0; j < words[i].length(); j++) {
//                char ch = words[i].charAt(j);
//                array2[ch - 'a']++;
//            }
//            boolean b = true;
//            for (int j = 0; j < 26; j++) {
//                if(array1[j]>array2[j]){
//                    b = false;
//                    break;
//                }
//            }
//            if (b && (index<0 || words[index].length()>words[i].length())){
//                index = i;
//            }
//        }
//        return words[index];
//    }
//}
//
//public class Manuscript{
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        String[] words = new String[]{"step","steps","stripe","stepple"};
//        String tmp = solution.shortestCompletingWord("1s3 PSt" ,words);
//        System.out.println(tmp);
//    }
//}




// 杨辉三角
//public class Manuscript{
//    public static List<List<Integer>> generate(int numRows){
//        List<List<Integer>> listNum = new ArrayList<>();
//        List<Integer> list1 = new ArrayList<>();
//        list1.add(1);
//        listNum.add(list1);
//        for (int i = 1; i < numRows; i++) {
//            List<Integer> list = new ArrayList<>();
//            list.add(1);
//            List<Integer> preRow = listNum.get(i-1);
//            for (int j = 1; j < i; j++) {
//                int num = preRow.get(j) + preRow.get(j-1);
//                list.add(num);
//            }
//            list.add(1);
//            listNum.add(list);
//        }
//        return listNum;
//    }
//
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            List<List<Integer>> pascalTriangle = generate(sc.nextInt());
//            for (int i = 0; i < pascalTriangle.size(); i++) {
//                for (int j = 0; j < pascalTriangle.get(i).size(); j++) {
//                    System.out.print(pascalTriangle.get(i).get(j)+ " ");
//                }
//                System.out.println();
//            }
//        }
//
//    }
//}



//编写程序数一下 1到 100 的所有整数中出现多少个数字9
//public class Manuscript {
//    public static void main(String[] args) {
//        int n =100;
//        int count =0;
//        for(int i =9;i<=100;i++){
//            if(i%10 == 9){
//                count++;
//            }
//            if(i/10 == 9){
//                count++;
//            }
//        }
//        System.out.println(count);
//    }
//
//}


//输出 1000 - 2000 之间所有的闰年
//public class Manuscript {
//    public static void main(String[] args) {
//        for(int i=1000;i<=2000;i++){
//            if(0 == i % 4 && 0 != i % 100 || 0 == i % 400){
//                System.out.println(i);
//            }
//        }
//    }
//}

//打印 1 - 100 之间所有的素数
//public class Manuscript {
//    public static void main(String[] args) {
//        for(int i =1;i<=100;i+=2) {
//            int j =0;
//            for( j = 2;j<=Math.sqrt(i);j++){
//                if(0 == i % j){
//                    break;
//                }
//            }
//            if(j>Math.sqrt(i)){
//                System.out.println(i);
//            }
//        }
//        System.out.println(2);
//    }
//}


//import java.util.Scanner;

//判定素数
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n  = scanner.nextInt();
//        int i=2;
//        for(i = 2;i< Math.sqrt(n);i++){
//            if(n % i == 0){
//                break;
//            }
//        }if(i> Math.sqrt(n)){
//            System.out.println("素数");
//        }else{
//            System.out.println("偶数");
//        }
//    }
//}

//import java.util.Scanner;
////根据输入的年龄, 来打印出当前年龄的人是少年(低于18), 青年(19-28), 中年(29-55), 老年(56以上)
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int i=scanner.nextInt();
//        if(0<i&&i<18){
//            System.out.println("少年");
//        }else if(i>=19 && i<=28){
//            System.out.println("青年");
//        }else if(i>=29 && i<=55){
//            System.out.println("中年");
//        } else{
//            System.out.println("老年");
//        }
//    }
//}

// 输出 X 图形
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args){
//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        int i =0;
//        for(i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                if(i==j || j == n-i-1){
//                    System.out.print("*");
//                }else{
//                    System.out.print(" ");
//                }
//            }System.out.print("\n");
//        }
//    }
//}

//输出 X 图形（多输入）
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner input = new Scanner(System.in);
//        while (input.hasNextInt()) {
//            int n = input.nextInt();
//            int i = 0;
//            for (i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (i == j || j == n - i - 1) {
//                        System.out.print("*");
//                    } else {
//                        System.out.print(" ");
//                    }
//                } System.out.print("\n");
//            }
//        }
//    }
//}

//完成猜数字游戏 ，用户输入数字，判断该数字是大于，小于，还是等于随机生成的数字，等于的时候退出程序
//import java.util.Random;
//import java.util.Scanner;
//
//public class Manuscript {
//
//    public static void menu(){
//        System.out.println("*****************");
//        System.out.println("**** 1.Play  ****");
//        System.out.println("**** 0.Exit  ****");
//        System.out.println("*****************");
//    }
//    public static void game(){
//      Scanner scanner = new Scanner(System.in);
//        Random random = new Random();//默认随机种子是系统时间
//         int toGuess = random.nextInt(100);
//        while(true){
//            System.out.println("请输入你所猜的数字");
//            int guess = scanner.nextInt();
//            if(guess < toGuess){
//                System.out.println("猜小了");
//            }else if(guess > toGuess){
//                System.out.println("猜大了");
//            }else{
//                System.out.println("猜对了");
//                break;
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int input = 0;
//        do{
//            menu();
//            System.out.println("请选择：");
//             input = scanner.nextInt();
//            switch(input){
//                case 1:{
//                    game();
//                    break;
//                } case 0:{
//                    System.out.println("退出游戏");
//                    break;
//                } default:{
//                    System.out.println("输入错误，请重新输入");
//                    break;
//                }
//
//            }
//        }while (input>0);
//
//    }
//}


//求出0～999之间的所有“水仙花数”并输出。(“水仙花数”是指一个三位数，其各位数字的立方和确好等于该数本 身，
// 如；153＝1＋5＋3?，则153是一个“水仙花数“。）

//public class Manuscript {
//
//    public static int place(int x){
//        int num = 1;
//        while(0!=x/10){
//            num++;
//            x = x/10;
//        }return num;
//    }
//    public static void judge(int x,int y){
//        if(y>2){
//            int tem = 0;
//            int ret = x;
//            int P =y;
//            while(y>0){
//                tem += (int)Math.pow(x%10,P);
//                x = x/10;
//                y--;
//            }if(tem == ret){
//                System.out.println(ret+"是水仙花数");
//            }
//        }
//
//    }
//
//    public static void main(String[] args) {
//        int n = 1000;
//        int count = 0;
//        int i = 0;
//        for(i =0;i<n;i++){
//              count = place(i);
//              judge(i,count);
//        }
//    }
//}


//import java.util.Scanner;

//计算1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 的值 。
//public class Manuscript {
//    public static void main(String[] args) {
//        double sum =0;
//        int flag = 1;
//        for(int i =1;i<101;i++){
//            sum += (1.0/i)*flag;
//            flag = -flag;
//        }
//        System.out.println(sum);
//    }
//}


//import java.util.Scanner;
//
////求两个正整数的最大公约数
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner input = new Scanner(System.in);
//        int a = input.nextInt();
//        int b = input.nextInt();
//        int c = 0;
//        while (0 != a % b) {
//            c = a % b;
//            a = b;
//            b = c;
//        }
//        System.out.println("最大公约数为" + b);
//    }
//}


//import java.util.Scanner;
//
////求一个整数，在内存当中存储时，二进制1的个数
//public class Manuscript{
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int input = scanner.nextInt();
//        int count =0;
//        int place=0;
//        while((place++)<32){
//            if(((input>>place) & 1) ==1){
//                count++;
//
//            }
//        }
//        System.out.println(count);
//
//    }
//}


//import java.util.Scanner;
//public class Manuscript{
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int input = scanner.nextInt();
//        int count =0;
//        int place=0;
//        while(input!=0){
//           count++;
//           input&=(input-1);
//        }
//
//        System.out.println(count);
//
//    }
//}




//获取一个数二进制序列中所有的偶数位和奇数位， 分别输出二进制序列
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int input = scanner.nextInt();
//        int  i =0;
//        System.out.println("偶数位");
//        for(i=0;i<32;i++){
//            if(i%2==0){
//                System.out.print(input&(1<<i));
//            }
//        }
//        System.out.println("\n");
//        System.out.println("奇数位");
//        for(i=0;i<32;i++){
//            if(i%2!=0){
//                System.out.print(input&(1<<i));
//            }
//        }
//    }
//}


//import java.util.Scanner;
////编写代码模拟三次密码输入的场景。 最多能输入三次密码，密码正确，提示“登录成功”,密码错误， 可以重新输 入，最多输入三次。三次均错，则提示退出程序
//public class Manuscript {
//    public static void main(String[] args) {
//     login();
//    }
//    public static void login(){
//        Scanner scanner = new Scanner(System.in);
//        int count =3;
//        while(count--!=0){
//            System.out.print("请输入登录密码：");
//            String password = scanner.nextLine();
//            if(password.equals("123456")){
//                System.out.println("登录成功！");
//                break;
//            }else{
//                System.out.println("密码错误！"+"你还剩"+count+"机会");
//            }
//            if(count==0){
//                System.out.println("已冻结");
//            }
//        }
//    }
//}


//输出一个整数的每一位，如：123的每一位是1 ， 2 ， 3

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int input = scanner.nextInt();
//        print(input);
//    }
//    public static void print(int n){
//        int place = count(n);
//        while(place-- != 0){
//            System.out.println(n/(int)(Math.pow(10,place)));
//            n%=(int)(Math.pow(10,place));
//        }
//    }
//    public static int count(int n){
//        int palce =1;
//        while(0!=n/10){
//            palce++;
//            n = n/10;
//        }
//        return  palce;
//    }
//}



//输出n*n的乘法口诀表，n由用户输入。

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请输入你想生成的n阶乘法口诀表：");
//        int n =scanner.nextInt();
//        print(n);
//    }
//    public static void print(int n){
//        int i =1;
//        for(i=1;i<=n;i++){
//            int j =1;
//            for(j=1;j<=i;j++){
//                System.out.print(j+"*"+i+"="+j*i+" ");
//            }
//            System.out.println();
//        }
//    }
//}



//import java.util.Scanner;
//
////求斐波那契数列的第n项。(迭代实现)
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        find(n);
//    }
//    public static void find(int n){
//        int a =1;
//        int b=1;
//        int c=1;
//        while(n>2){
//            c = b + a;
//            a=b;
//            b=c;
//            n--;
//        }
//        System.out.println(c);
//    }
//}'

//import java.util.Scanner;
//
////求阶乘和
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        FactorialSum(n);
//    }
//    public static void FactorialSum(int n){
//        int sum = 0;
//        int ret =1;
//        for(int i =1;i<=n;i++){
//            ret *= i;
//            sum+=ret;
//        }
//        System.out.println(sum);
//    }
//}




//求阶乘
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        FactorialSum(n);
//    }
//    public static void FactorialSum(int n){
//        int ret =1;
//        for(int i =1;i<=n;i++){
//            ret *= i;
//        }
//        System.out.println(ret);
//    }
//}

//创建方法求两个数的最大值max2，随后再写一个求3个数的最大值的函数max3。
//
//     要求：在max3这个函数中，调用max2函数，来实现3个数的最大值计算

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int a = scanner.nextInt();
//        int b = scanner.nextInt();
//        int c = scanner.nextInt();
//        max3(a,b,c);
//    }
//    public static void max3(int x,int y,int z){
//        int ret = max2(x,y);
//        int max = max2(ret,z);
//        System.out.println(max);
//    }
//    public static  int max2(int x,int y){
//        return (x>y?x:y);
//    }
//}

//求最大值方法的重载
//在同一个类中定义多个方法：要求不仅可以求两个整数的最大值，还可以求两个小数的最大值，以及两个小数和一个整数的大小关系

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int a = scanner.nextInt();
//        int b = scanner.nextInt();
//        double c = scanner.nextDouble();
//        double d = scanner.nextDouble();
//        max(a,b);
//        max(c,d);
//        max(c,d,a);
//    }
//    public static void max(int x,int y){
//        int ret =x>y?x:y;
//        System.out.println(ret);
//    }
//    public  static void max(double x,double y){
//        double ret = x>y?x:y;
//        System.out.println(ret);
//    }
//    public  static  void max(double x,double y,int z){
//        double ret = x>y?x:y;
//        System.out.println(ret>z?ret:z);
//    }
//}


//import java.util.Scanner;
//
////求和的重载
////在同一个类中,分别定义求两个整数的方法 和 三个小数之和的方法。 并执行代码，求出结果
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int a = scanner.nextInt();
//        int b = scanner.nextInt();
//        double c = scanner.nextDouble();
//        double d = scanner.nextDouble();
//        double e = scanner.nextDouble();
//        sum(a,b);
//        sum(c,d,e);
//    }
//    public  static  void sum(int x,int y){
//        System.out.println(x+y);
//    }
//    public  static  void sum(double x,double y,double z){
//        System.out.println(x+y+z);
//    }
//}

//奇数 位于 偶数之前
//调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入你的数列，且用逗号隔开：");
//        Scanner scanner = new Scanner(System.in);
//        String str = scanner.nextLine();
//        String[] arr = str.split(",");
//        int[] a = new int[arr.length];
//        for (int i = 0; i < arr.length; i++) {
//            a[i] = Integer.parseInt(arr[i]);
//        }
//        for (int j = 0; j < a.length; j++) {
//            if(a[j]%2!=0){
//                j++;
//                if(j == a.length){// 全奇数数组
//                    break;
//                }
//            }
//            int i = 0;
//            for (i = j; i < a.length; i++) {
//                if (a[i] % 2 != 0) {
//                    int tmp = a[j];
//                    a[j] = a[i];
//                    a[i] = tmp;
//                    break;
//                }
//            }
//            if(i == a.length){// 后面部分全偶数/全偶数数组
//                break;
//            }
//        }
//        for(int i = 0;i< a.length;i++){
//            System.out.print(a[i]);
//        }
//    }
//}

//有一组数据，只有一个数字是出现一次，其他是两次，请找出这个数



//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入你数列（只有一个数字是单次出现，其他都是成双,且用逗号隔开）：");
//        Scanner sc =new Scanner(System.in);
//        String str = sc.next().toString();
//        String[] arr = str.split(",");
//
//        int [] a = new int[arr.length];
//        for (int j =0;j<a.length;j++){
//            a[j]=Integer.parseInt(arr[j]);
//        }
//        int m = a[0];
//        for (int i =1;i<a.length;i++){
//            m^=a[i];
//        }
//        System.out.println(m);
//        sc.close();
//    }
//}



//青蛙跳台阶问题
//import java.util.Scanner;
//public  class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        fogJump(n);
//scanner.close();
//    }
//    public static void fogJump(int n){
//        int floor = n;
//        if(n<3){
//            System.out.println("青蛙上"+n+"阶台阶有"+n+"种跳法");
//        }else{
//            int f1 = 1;
//            int f2 = 2;
//            int f3 = 0;
//            while(n>2){
//                f3 = f2+f1;
//                f1 = f2;
//                f2 = f3;
//                n--;
//            }
//            System.out.println("青蛙上"+floor+"阶台阶有"+f3+"种跳法");
//        }
//    }
//}

//递归求斐波那契数列的第 N 项
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        System.out.println(fibonacci(n));
//scanner.close();
//    }
//    public static int fibonacci(int n){
//        if(n<2){
//            return  1;
//        }else{
//            return fibonacci(n-1)+fibonacci(n-2);
//        }
//
//    }
//}


//返回的数字之和
//写一个递归方法，输入一个非负整数，返回组成它的数字之和
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        System.out.println(sumadd(n));
//scanner.close();
//    }
//    public static int sumadd(int n){
//        int sum=0;
//        if(n<10){
//            return n;
//        }else{
//             sum = n%10+sumadd(n/10);
//        }
//        return  sum;
//    }
//}


//按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4) （递归）

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        print(n);
//scanner.close();
//    }
//    public static void print(int n){
//        if(n<10){
//            System.out.println(n);
//        }else{
//            print(n/10);
//            System.out.println(n%10);
//        }
//    }
//}


//递归求和

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        System.out.println(sumadd(n));
//scanner.close();
//    }
//    public static int sumadd(int n){
//        if(1==n){
//            return 1;
//        }
//        return n+sumadd(n-1);
//    }
//}

//递归求 N 的阶乘

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        System.out.println(factorial(n));
//scanner.close();
//    }
//    public static int factorial(int n){
//        if(1==n){
//            return 1;
//        }
//        return n*factorial(n-1);
//    }
//}


//递归求解汉诺塔问题

//import java.util.Scanner;
//
//public class Manuscript {
//    static int times;// 移动次数
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        char A = 'A';
//        char B = 'B';
//        char C = 'C';
//        int n = scanner.nextInt();
//        game(n,A,B,C);
//        scanner.close();
//    }
//    public static void move(int disk,char M,char N){
//        System.out.println("第"+(++times)+"次移动，盘子"+disk+" "+M +"---->"+N);
//
//    }
//    public static void game(int n,char A,char B,char C){
//        if(n==1){
//            move(n,A,C);
//        }else{
//            // 将 n-1 个 盘子 放到B柱子
//            game(n-1,A,C,B);
//
//            move(n,A,C);
//            // 把n-1 个盘子 放在C上
//            game(n-1,B,A,C);
//        }
//    }
//}


//实现一个方法 avg, 以数组为参数, 求数组中所有元素的平均值(注意方法的返回值类型


//import java.util.Scanner;
//
//public class Manuscript{
//    public static void main(String[] args) {
//        System.out.println("求输入一组数字，用逗号隔开");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        System.out.println(average(array));
//        sc.close();
//    }
//    public static int average(int[] array){
//        int sum =0;
//        for (int i = 0; i < array.length; i++) {
//            sum+=array[i];
//        }
//        return sum/array.length;
//    }
//}

//实现一个方法 sum, 以数组为参数, 求数组所有元素之和.

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，用逗号分开：");
//        Scanner sc = new Scanner(System.in);
//        String  str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        System.out.println(sum(array));
//        sc.close();
//    }
//    public static int sum(int[] array){
//        int sum =0;
//        for (int i = 0; i < array.length; i++) {
//            sum+=array[i];
//        }
//        return sum;
//    }
//}

//实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2
// 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
//import java.util.Arrays;
//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，用逗号分开：");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length ; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        rid(array);
//        System.out.println(Arrays.toString(array));
//        sc.close();
//    }
//    public static void rid(int[] array){
//        for (int i = 0; i < array.length; i++) {
//            array[i]= 2*array[i];
//        }
//    }
//}


//实现一个方法 printArray, 以数组为参数, 循环访问数组中的每个元素, 打印每个元素的值

//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，用逗号隔开：");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        printArray(array);
//        sc.close();
//    }
//    public static void printArray(int[] array){
//        for (int x:array) {
//            System.out.print(x+" ");
//        }
//        System.out.println();
//    }
//}


//创建一个 int 类型的数组, 元素个数为 100, 并把每个元素依次设置为 1 - 100

//import java.util.Arrays;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        int[] array = new int[100];
//        initialize(array);
//        System.out.println(Arrays.toString(array));
//    }
//    public static void initialize(int[] array){
//        for (int i = 0; i < array.length; i++) {
//            array[i]=1+i;
//        }
//    }
//}


//冒泡排序


//import java.util.Arrays;
//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，用逗号隔开");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        bubbleSort(array);
//        System.out.println(Arrays.toString(array));
//        sc.close();
//    }
//    public static void bubbleSort(int[] array){
//        for (int i = 0; i < array.length-1; i++) {
//            int flag=1;// 假设这一趟数据已经有序
//
//            // 每一天排序的过程
//            for (int j = 0; j < array.length-i-1; j++) {
//                if(array[j]>array[j+1]){
//                    int tmp = array[j];
//                    array[j] = array[j+1];
//                    array[j+1] = tmp;
//                    flag = 0;
//                }
//
//            }
//            if(1==flag){
//                break;
//            }
//
//        }
//    }
//}


//数组是否有序


//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，用逗号隔开");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        int flag = bubbleSort(array);
//        if(1==flag){
//            System.out.println("有序");
//        }else{
//            System.out.println("无序");
//        }
//
//        sc.close();
//    }
//    public static int bubbleSort(int[] array){
//        int flag=1;
//        for (int i = 0; i < array.length-1; i++) {
//                if(array[i]>array[i+1]){
//                    flag = 0;
//                    return flag;
//                }
//            }
//        return flag;
//        }
//}

//给定一个有序整型数组, 实现二分查找
//import java.util.Scanner;
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组有序数列，用逗号隔开");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        System.out.print("请输入你要查找的数：");
//        int key = sc.nextInt();// 要查找的数
//        if(-1==binarySearch(array,key)){
//            System.out.println("你要查找的数不存在。");
//        }else{
//            System.out.println("找到了，下标为："+binarySearch(array,key));
//        }
//        sc.close();
//    }
//    public static int binarySearch(int[] array,int key){
//        int right = array.length-1;
//        int left = 0;
//        int mid = 0;
//        while(right>left){
//            mid = (right+left)/2;
//            if(array[mid]>key){
//                right--;
//            }
//            if(array[mid]<key){
//                left++;
//            }else {
//                return mid;
//            }
//        }
//        return -1;
//    }
//}


//实现一个方法 copyOf, 对一个整型数组进行拷贝, 得到一个新的数组

//import java.util.Arrays;
//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("输入一组数列，用逗号隔开：");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int array[] = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        int[] array2 = copyOf(array);
//        System.out.println(Arrays.toString(array2));
//        sc.close();
//    }
//    public static int[] copyOf(int[] array){
//        int[] ret = new int[array.length];
//        for (int i = 0; i < array.length; i++) {
//            ret[i]=array[i];
//        }
//        return ret;
//    }
//}



//实现一个方法 toString, 把一个整型数组转换成字符串. 例如数组 {1, 2, 3} , 返回的字符串为 "[1, 2, 3]", 注意 逗号 的位置和数量.
//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int array[] = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i] = Integer.parseInt(str1[i]);
//        }
//        String str2 = myToString(array);
//        System.out.println(str2);
//        sc.close();
//    }
//    public static String myToString(int[] array){
//        String str = "[";
//        for (int i = 0; i < array.length; i++) {
//            str+=array[i];
//            if(i< array.length-1){
//                str+=",";
//            }
//        }
//        str+="]";
//        return str;
//    }
//}

//给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
//import java.util.Scanner;
//
//public class Manuscript {
//    public static void main(String[] args) {
//        System.out.println("请输入一组数列，只有一个数字是单独出现的，且用逗号隔开");
//        Scanner sc = new Scanner(System.in);
//        String str = sc.nextLine();
//        String[] str1 = str.split(",");
//        int[] array = new int[str1.length];
//        for (int i = 0; i < str1.length; i++) {
//            array[i]=Integer.parseInt(str1[i]);
//        }
//        System.out.println(findOne(array));
//        sc.close();
//    }
//    public static int findOne(int[] array){
//        int m = array[0];
//        for (int i = 1; i < array.length; i++) {
//            m ^=array[i];
//        }
//        return m;
//    }
//}


